libstdc++
|
00001 // Algorithm implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2015 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 <bits/uniform_int_dist.h> 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 inline namespace _V2 01241 { 01242 01243 /// This is a helper function for the rotate algorithm. 01244 template<typename _ForwardIterator> 01245 _ForwardIterator 01246 __rotate(_ForwardIterator __first, 01247 _ForwardIterator __middle, 01248 _ForwardIterator __last, 01249 forward_iterator_tag) 01250 { 01251 if (__first == __middle) 01252 return __last; 01253 else if (__last == __middle) 01254 return __first; 01255 01256 _ForwardIterator __first2 = __middle; 01257 do 01258 { 01259 std::iter_swap(__first, __first2); 01260 ++__first; 01261 ++__first2; 01262 if (__first == __middle) 01263 __middle = __first2; 01264 } 01265 while (__first2 != __last); 01266 01267 _ForwardIterator __ret = __first; 01268 01269 __first2 = __middle; 01270 01271 while (__first2 != __last) 01272 { 01273 std::iter_swap(__first, __first2); 01274 ++__first; 01275 ++__first2; 01276 if (__first == __middle) 01277 __middle = __first2; 01278 else if (__first2 == __last) 01279 __first2 = __middle; 01280 } 01281 return __ret; 01282 } 01283 01284 /// This is a helper function for the rotate algorithm. 01285 template<typename _BidirectionalIterator> 01286 _BidirectionalIterator 01287 __rotate(_BidirectionalIterator __first, 01288 _BidirectionalIterator __middle, 01289 _BidirectionalIterator __last, 01290 bidirectional_iterator_tag) 01291 { 01292 // concept requirements 01293 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 01294 _BidirectionalIterator>) 01295 01296 if (__first == __middle) 01297 return __last; 01298 else if (__last == __middle) 01299 return __first; 01300 01301 std::__reverse(__first, __middle, bidirectional_iterator_tag()); 01302 std::__reverse(__middle, __last, bidirectional_iterator_tag()); 01303 01304 while (__first != __middle && __middle != __last) 01305 { 01306 std::iter_swap(__first, --__last); 01307 ++__first; 01308 } 01309 01310 if (__first == __middle) 01311 { 01312 std::__reverse(__middle, __last, bidirectional_iterator_tag()); 01313 return __last; 01314 } 01315 else 01316 { 01317 std::__reverse(__first, __middle, bidirectional_iterator_tag()); 01318 return __first; 01319 } 01320 } 01321 01322 /// This is a helper function for the rotate algorithm. 01323 template<typename _RandomAccessIterator> 01324 _RandomAccessIterator 01325 __rotate(_RandomAccessIterator __first, 01326 _RandomAccessIterator __middle, 01327 _RandomAccessIterator __last, 01328 random_access_iterator_tag) 01329 { 01330 // concept requirements 01331 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 01332 _RandomAccessIterator>) 01333 01334 if (__first == __middle) 01335 return __last; 01336 else if (__last == __middle) 01337 return __first; 01338 01339 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 01340 _Distance; 01341 typedef typename iterator_traits<_RandomAccessIterator>::value_type 01342 _ValueType; 01343 01344 _Distance __n = __last - __first; 01345 _Distance __k = __middle - __first; 01346 01347 if (__k == __n - __k) 01348 { 01349 std::swap_ranges(__first, __middle, __middle); 01350 return __middle; 01351 } 01352 01353 _RandomAccessIterator __p = __first; 01354 _RandomAccessIterator __ret = __first + (__last - __middle); 01355 01356 for (;;) 01357 { 01358 if (__k < __n - __k) 01359 { 01360 if (__is_pod(_ValueType) && __k == 1) 01361 { 01362 _ValueType __t = _GLIBCXX_MOVE(*__p); 01363 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p); 01364 *(__p + __n - 1) = _GLIBCXX_MOVE(__t); 01365 return __ret; 01366 } 01367 _RandomAccessIterator __q = __p + __k; 01368 for (_Distance __i = 0; __i < __n - __k; ++ __i) 01369 { 01370 std::iter_swap(__p, __q); 01371 ++__p; 01372 ++__q; 01373 } 01374 __n %= __k; 01375 if (__n == 0) 01376 return __ret; 01377 std::swap(__n, __k); 01378 __k = __n - __k; 01379 } 01380 else 01381 { 01382 __k = __n - __k; 01383 if (__is_pod(_ValueType) && __k == 1) 01384 { 01385 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1)); 01386 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n); 01387 *__p = _GLIBCXX_MOVE(__t); 01388 return __ret; 01389 } 01390 _RandomAccessIterator __q = __p + __n; 01391 __p = __q - __k; 01392 for (_Distance __i = 0; __i < __n - __k; ++ __i) 01393 { 01394 --__p; 01395 --__q; 01396 std::iter_swap(__p, __q); 01397 } 01398 __n %= __k; 01399 if (__n == 0) 01400 return __ret; 01401 std::swap(__n, __k); 01402 } 01403 } 01404 } 01405 01406 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01407 // DR 488. rotate throws away useful information 01408 /** 01409 * @brief Rotate the elements of a sequence. 01410 * @ingroup mutating_algorithms 01411 * @param __first A forward iterator. 01412 * @param __middle A forward iterator. 01413 * @param __last A forward iterator. 01414 * @return first + (last - middle). 01415 * 01416 * Rotates the elements of the range @p [__first,__last) by 01417 * @p (__middle - __first) positions so that the element at @p __middle 01418 * is moved to @p __first, the element at @p __middle+1 is moved to 01419 * @p __first+1 and so on for each element in the range 01420 * @p [__first,__last). 01421 * 01422 * This effectively swaps the ranges @p [__first,__middle) and 01423 * @p [__middle,__last). 01424 * 01425 * Performs 01426 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n) 01427 * for each @p n in the range @p [0,__last-__first). 01428 */ 01429 template<typename _ForwardIterator> 01430 inline _ForwardIterator 01431 rotate(_ForwardIterator __first, _ForwardIterator __middle, 01432 _ForwardIterator __last) 01433 { 01434 // concept requirements 01435 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01436 _ForwardIterator>) 01437 __glibcxx_requires_valid_range(__first, __middle); 01438 __glibcxx_requires_valid_range(__middle, __last); 01439 01440 return std::__rotate(__first, __middle, __last, 01441 std::__iterator_category(__first)); 01442 } 01443 01444 } // namespace _V2 01445 01446 /** 01447 * @brief Copy a sequence, rotating its elements. 01448 * @ingroup mutating_algorithms 01449 * @param __first A forward iterator. 01450 * @param __middle A forward iterator. 01451 * @param __last A forward iterator. 01452 * @param __result An output iterator. 01453 * @return An iterator designating the end of the resulting sequence. 01454 * 01455 * Copies the elements of the range @p [__first,__last) to the 01456 * range beginning at @result, rotating the copied elements by 01457 * @p (__middle-__first) positions so that the element at @p __middle 01458 * is moved to @p __result, the element at @p __middle+1 is moved 01459 * to @p __result+1 and so on for each element in the range @p 01460 * [__first,__last). 01461 * 01462 * Performs 01463 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n) 01464 * for each @p n in the range @p [0,__last-__first). 01465 */ 01466 template<typename _ForwardIterator, typename _OutputIterator> 01467 inline _OutputIterator 01468 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, 01469 _ForwardIterator __last, _OutputIterator __result) 01470 { 01471 // concept requirements 01472 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 01473 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 01474 typename iterator_traits<_ForwardIterator>::value_type>) 01475 __glibcxx_requires_valid_range(__first, __middle); 01476 __glibcxx_requires_valid_range(__middle, __last); 01477 01478 return std::copy(__first, __middle, 01479 std::copy(__middle, __last, __result)); 01480 } 01481 01482 /// This is a helper function... 01483 template<typename _ForwardIterator, typename _Predicate> 01484 _ForwardIterator 01485 __partition(_ForwardIterator __first, _ForwardIterator __last, 01486 _Predicate __pred, forward_iterator_tag) 01487 { 01488 if (__first == __last) 01489 return __first; 01490 01491 while (__pred(*__first)) 01492 if (++__first == __last) 01493 return __first; 01494 01495 _ForwardIterator __next = __first; 01496 01497 while (++__next != __last) 01498 if (__pred(*__next)) 01499 { 01500 std::iter_swap(__first, __next); 01501 ++__first; 01502 } 01503 01504 return __first; 01505 } 01506 01507 /// This is a helper function... 01508 template<typename _BidirectionalIterator, typename _Predicate> 01509 _BidirectionalIterator 01510 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, 01511 _Predicate __pred, bidirectional_iterator_tag) 01512 { 01513 while (true) 01514 { 01515 while (true) 01516 if (__first == __last) 01517 return __first; 01518 else if (__pred(*__first)) 01519 ++__first; 01520 else 01521 break; 01522 --__last; 01523 while (true) 01524 if (__first == __last) 01525 return __first; 01526 else if (!bool(__pred(*__last))) 01527 --__last; 01528 else 01529 break; 01530 std::iter_swap(__first, __last); 01531 ++__first; 01532 } 01533 } 01534 01535 // partition 01536 01537 /// This is a helper function... 01538 /// Requires __first != __last and !__pred(__first) 01539 /// and __len == distance(__first, __last). 01540 /// 01541 /// !__pred(__first) allows us to guarantee that we don't 01542 /// move-assign an element onto itself. 01543 template<typename _ForwardIterator, typename _Pointer, typename _Predicate, 01544 typename _Distance> 01545 _ForwardIterator 01546 __stable_partition_adaptive(_ForwardIterator __first, 01547 _ForwardIterator __last, 01548 _Predicate __pred, _Distance __len, 01549 _Pointer __buffer, 01550 _Distance __buffer_size) 01551 { 01552 if (__len == 1) 01553 return __first; 01554 01555 if (__len <= __buffer_size) 01556 { 01557 _ForwardIterator __result1 = __first; 01558 _Pointer __result2 = __buffer; 01559 01560 // The precondition guarantees that !__pred(__first), so 01561 // move that element to the buffer before starting the loop. 01562 // This ensures that we only call __pred once per element. 01563 *__result2 = _GLIBCXX_MOVE(*__first); 01564 ++__result2; 01565 ++__first; 01566 for (; __first != __last; ++__first) 01567 if (__pred(__first)) 01568 { 01569 *__result1 = _GLIBCXX_MOVE(*__first); 01570 ++__result1; 01571 } 01572 else 01573 { 01574 *__result2 = _GLIBCXX_MOVE(*__first); 01575 ++__result2; 01576 } 01577 01578 _GLIBCXX_MOVE3(__buffer, __result2, __result1); 01579 return __result1; 01580 } 01581 01582 _ForwardIterator __middle = __first; 01583 std::advance(__middle, __len / 2); 01584 _ForwardIterator __left_split = 01585 std::__stable_partition_adaptive(__first, __middle, __pred, 01586 __len / 2, __buffer, 01587 __buffer_size); 01588 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 01595 if (__right_len) 01596 __right_split = 01597 std::__stable_partition_adaptive(__right_split, __last, __pred, 01598 __right_len, 01599 __buffer, __buffer_size); 01600 01601 std::rotate(__left_split, __middle, __right_split); 01602 std::advance(__left_split, std::distance(__middle, __right_split)); 01603 return __left_split; 01604 } 01605 01606 template<typename _ForwardIterator, typename _Predicate> 01607 _ForwardIterator 01608 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, 01609 _Predicate __pred) 01610 { 01611 __first = std::__find_if_not(__first, __last, __pred); 01612 01613 if (__first == __last) 01614 return __first; 01615 01616 typedef typename iterator_traits<_ForwardIterator>::value_type 01617 _ValueType; 01618 typedef typename iterator_traits<_ForwardIterator>::difference_type 01619 _DistanceType; 01620 01621 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last); 01622 return 01623 std::__stable_partition_adaptive(__first, __last, __pred, 01624 _DistanceType(__buf.requested_size()), 01625 __buf.begin(), 01626 _DistanceType(__buf.size())); 01627 } 01628 01629 /** 01630 * @brief Move elements for which a predicate is true to the beginning 01631 * of a sequence, preserving relative ordering. 01632 * @ingroup mutating_algorithms 01633 * @param __first A forward iterator. 01634 * @param __last A forward iterator. 01635 * @param __pred A predicate functor. 01636 * @return An iterator @p middle such that @p __pred(i) is true for each 01637 * iterator @p i in the range @p [first,middle) and false for each @p i 01638 * in the range @p [middle,last). 01639 * 01640 * Performs the same function as @p partition() with the additional 01641 * guarantee that the relative ordering of elements in each group is 01642 * preserved, so any two elements @p x and @p y in the range 01643 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same 01644 * relative ordering after calling @p stable_partition(). 01645 */ 01646 template<typename _ForwardIterator, typename _Predicate> 01647 inline _ForwardIterator 01648 stable_partition(_ForwardIterator __first, _ForwardIterator __last, 01649 _Predicate __pred) 01650 { 01651 // concept requirements 01652 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01653 _ForwardIterator>) 01654 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 01655 typename iterator_traits<_ForwardIterator>::value_type>) 01656 __glibcxx_requires_valid_range(__first, __last); 01657 01658 return std::__stable_partition(__first, __last, 01659 __gnu_cxx::__ops::__pred_iter(__pred)); 01660 } 01661 01662 /// This is a helper function for the sort routines. 01663 template<typename _RandomAccessIterator, typename _Compare> 01664 void 01665 __heap_select(_RandomAccessIterator __first, 01666 _RandomAccessIterator __middle, 01667 _RandomAccessIterator __last, _Compare __comp) 01668 { 01669 std::__make_heap(__first, __middle, __comp); 01670 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 01671 if (__comp(__i, __first)) 01672 std::__pop_heap(__first, __middle, __i, __comp); 01673 } 01674 01675 // partial_sort 01676 01677 template<typename _InputIterator, typename _RandomAccessIterator, 01678 typename _Compare> 01679 _RandomAccessIterator 01680 __partial_sort_copy(_InputIterator __first, _InputIterator __last, 01681 _RandomAccessIterator __result_first, 01682 _RandomAccessIterator __result_last, 01683 _Compare __comp) 01684 { 01685 typedef typename iterator_traits<_InputIterator>::value_type 01686 _InputValueType; 01687 typedef iterator_traits<_RandomAccessIterator> _RItTraits; 01688 typedef typename _RItTraits::difference_type _DistanceType; 01689 01690 if (__result_first == __result_last) 01691 return __result_last; 01692 _RandomAccessIterator __result_real_last = __result_first; 01693 while (__first != __last && __result_real_last != __result_last) 01694 { 01695 *__result_real_last = *__first; 01696 ++__result_real_last; 01697 ++__first; 01698 } 01699 01700 std::__make_heap(__result_first, __result_real_last, __comp); 01701 while (__first != __last) 01702 { 01703 if (__comp(__first, __result_first)) 01704 std::__adjust_heap(__result_first, _DistanceType(0), 01705 _DistanceType(__result_real_last 01706 - __result_first), 01707 _InputValueType(*__first), __comp); 01708 ++__first; 01709 } 01710 std::__sort_heap(__result_first, __result_real_last, __comp); 01711 return __result_real_last; 01712 } 01713 01714 /** 01715 * @brief Copy the smallest elements of a sequence. 01716 * @ingroup sorting_algorithms 01717 * @param __first An iterator. 01718 * @param __last Another iterator. 01719 * @param __result_first A random-access iterator. 01720 * @param __result_last Another random-access iterator. 01721 * @return An iterator indicating the end of the resulting sequence. 01722 * 01723 * Copies and sorts the smallest N values from the range @p [__first,__last) 01724 * to the range beginning at @p __result_first, where the number of 01725 * elements to be copied, @p N, is the smaller of @p (__last-__first) and 01726 * @p (__result_last-__result_first). 01727 * After the sort if @e i and @e j are iterators in the range 01728 * @p [__result_first,__result_first+N) such that i precedes j then 01729 * *j<*i is false. 01730 * The value returned is @p __result_first+N. 01731 */ 01732 template<typename _InputIterator, typename _RandomAccessIterator> 01733 inline _RandomAccessIterator 01734 partial_sort_copy(_InputIterator __first, _InputIterator __last, 01735 _RandomAccessIterator __result_first, 01736 _RandomAccessIterator __result_last) 01737 { 01738 typedef typename iterator_traits<_InputIterator>::value_type 01739 _InputValueType; 01740 typedef typename iterator_traits<_RandomAccessIterator>::value_type 01741 _OutputValueType; 01742 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 01743 _DistanceType; 01744 01745 // concept requirements 01746 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 01747 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 01748 _OutputValueType>) 01749 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType, 01750 _OutputValueType>) 01751 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>) 01752 __glibcxx_requires_valid_range(__first, __last); 01753 __glibcxx_requires_valid_range(__result_first, __result_last); 01754 01755 return std::__partial_sort_copy(__first, __last, 01756 __result_first, __result_last, 01757 __gnu_cxx::__ops::__iter_less_iter()); 01758 } 01759 01760 /** 01761 * @brief Copy the smallest elements of a sequence using a predicate for 01762 * comparison. 01763 * @ingroup sorting_algorithms 01764 * @param __first An input iterator. 01765 * @param __last Another input iterator. 01766 * @param __result_first A random-access iterator. 01767 * @param __result_last Another random-access iterator. 01768 * @param __comp A comparison functor. 01769 * @return An iterator indicating the end of the resulting sequence. 01770 * 01771 * Copies and sorts the smallest N values from the range @p [__first,__last) 01772 * to the range beginning at @p result_first, where the number of 01773 * elements to be copied, @p N, is the smaller of @p (__last-__first) and 01774 * @p (__result_last-__result_first). 01775 * After the sort if @e i and @e j are iterators in the range 01776 * @p [__result_first,__result_first+N) such that i precedes j then 01777 * @p __comp(*j,*i) is false. 01778 * The value returned is @p __result_first+N. 01779 */ 01780 template<typename _InputIterator, typename _RandomAccessIterator, 01781 typename _Compare> 01782 inline _RandomAccessIterator 01783 partial_sort_copy(_InputIterator __first, _InputIterator __last, 01784 _RandomAccessIterator __result_first, 01785 _RandomAccessIterator __result_last, 01786 _Compare __comp) 01787 { 01788 typedef typename iterator_traits<_InputIterator>::value_type 01789 _InputValueType; 01790 typedef typename iterator_traits<_RandomAccessIterator>::value_type 01791 _OutputValueType; 01792 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 01793 _DistanceType; 01794 01795 // concept requirements 01796 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 01797 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 01798 _RandomAccessIterator>) 01799 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 01800 _OutputValueType>) 01801 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 01802 _InputValueType, _OutputValueType>) 01803 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 01804 _OutputValueType, _OutputValueType>) 01805 __glibcxx_requires_valid_range(__first, __last); 01806 __glibcxx_requires_valid_range(__result_first, __result_last); 01807 01808 return std::__partial_sort_copy(__first, __last, 01809 __result_first, __result_last, 01810 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 01811 } 01812 01813 /// This is a helper function for the sort routine. 01814 template<typename _RandomAccessIterator, typename _Compare> 01815 void 01816 __unguarded_linear_insert(_RandomAccessIterator __last, 01817 _Compare __comp) 01818 { 01819 typename iterator_traits<_RandomAccessIterator>::value_type 01820 __val = _GLIBCXX_MOVE(*__last); 01821 _RandomAccessIterator __next = __last; 01822 --__next; 01823 while (__comp(__val, __next)) 01824 { 01825 *__last = _GLIBCXX_MOVE(*__next); 01826 __last = __next; 01827 --__next; 01828 } 01829 *__last = _GLIBCXX_MOVE(__val); 01830 } 01831 01832 /// This is a helper function for the sort routine. 01833 template<typename _RandomAccessIterator, typename _Compare> 01834 void 01835 __insertion_sort(_RandomAccessIterator __first, 01836 _RandomAccessIterator __last, _Compare __comp) 01837 { 01838 if (__first == __last) return; 01839 01840 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 01841 { 01842 if (__comp(__i, __first)) 01843 { 01844 typename iterator_traits<_RandomAccessIterator>::value_type 01845 __val = _GLIBCXX_MOVE(*__i); 01846 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); 01847 *__first = _GLIBCXX_MOVE(__val); 01848 } 01849 else 01850 std::__unguarded_linear_insert(__i, 01851 __gnu_cxx::__ops::__val_comp_iter(__comp)); 01852 } 01853 } 01854 01855 /// This is a helper function for the sort routine. 01856 template<typename _RandomAccessIterator, typename _Compare> 01857 inline void 01858 __unguarded_insertion_sort(_RandomAccessIterator __first, 01859 _RandomAccessIterator __last, _Compare __comp) 01860 { 01861 for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 01862 std::__unguarded_linear_insert(__i, 01863 __gnu_cxx::__ops::__val_comp_iter(__comp)); 01864 } 01865 01866 /** 01867 * @doctodo 01868 * This controls some aspect of the sort routines. 01869 */ 01870 enum { _S_threshold = 16 }; 01871 01872 /// This is a helper function for the sort routine. 01873 template<typename _RandomAccessIterator, typename _Compare> 01874 void 01875 __final_insertion_sort(_RandomAccessIterator __first, 01876 _RandomAccessIterator __last, _Compare __comp) 01877 { 01878 if (__last - __first > int(_S_threshold)) 01879 { 01880 std::__insertion_sort(__first, __first + int(_S_threshold), __comp); 01881 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, 01882 __comp); 01883 } 01884 else 01885 std::__insertion_sort(__first, __last, __comp); 01886 } 01887 01888 /// This is a helper function... 01889 template<typename _RandomAccessIterator, typename _Compare> 01890 _RandomAccessIterator 01891 __unguarded_partition(_RandomAccessIterator __first, 01892 _RandomAccessIterator __last, 01893 _RandomAccessIterator __pivot, _Compare __comp) 01894 { 01895 while (true) 01896 { 01897 while (__comp(__first, __pivot)) 01898 ++__first; 01899 --__last; 01900 while (__comp(__pivot, __last)) 01901 --__last; 01902 if (!(__first < __last)) 01903 return __first; 01904 std::iter_swap(__first, __last); 01905 ++__first; 01906 } 01907 } 01908 01909 /// This is a helper function... 01910 template<typename _RandomAccessIterator, typename _Compare> 01911 inline _RandomAccessIterator 01912 __unguarded_partition_pivot(_RandomAccessIterator __first, 01913 _RandomAccessIterator __last, _Compare __comp) 01914 { 01915 _RandomAccessIterator __mid = __first + (__last - __first) / 2; 01916 std::__move_median_to_first(__first, __first + 1, __mid, __last - 1, 01917 __comp); 01918 return std::__unguarded_partition(__first + 1, __last, __first, __comp); 01919 } 01920 01921 template<typename _RandomAccessIterator, typename _Compare> 01922 inline void 01923 __partial_sort(_RandomAccessIterator __first, 01924 _RandomAccessIterator __middle, 01925 _RandomAccessIterator __last, 01926 _Compare __comp) 01927 { 01928 std::__heap_select(__first, __middle, __last, __comp); 01929 std::__sort_heap(__first, __middle, __comp); 01930 } 01931 01932 /// This is a helper function for the sort routine. 01933 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 01934 void 01935 __introsort_loop(_RandomAccessIterator __first, 01936 _RandomAccessIterator __last, 01937 _Size __depth_limit, _Compare __comp) 01938 { 01939 while (__last - __first > int(_S_threshold)) 01940 { 01941 if (__depth_limit == 0) 01942 { 01943 std::__partial_sort(__first, __last, __last, __comp); 01944 return; 01945 } 01946 --__depth_limit; 01947 _RandomAccessIterator __cut = 01948 std::__unguarded_partition_pivot(__first, __last, __comp); 01949 std::__introsort_loop(__cut, __last, __depth_limit, __comp); 01950 __last = __cut; 01951 } 01952 } 01953 01954 // sort 01955 01956 template<typename _RandomAccessIterator, typename _Compare> 01957 inline void 01958 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 01959 _Compare __comp) 01960 { 01961 if (__first != __last) 01962 { 01963 std::__introsort_loop(__first, __last, 01964 std::__lg(__last - __first) * 2, 01965 __comp); 01966 std::__final_insertion_sort(__first, __last, __comp); 01967 } 01968 } 01969 01970 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 01971 void 01972 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, 01973 _RandomAccessIterator __last, _Size __depth_limit, 01974 _Compare __comp) 01975 { 01976 while (__last - __first > 3) 01977 { 01978 if (__depth_limit == 0) 01979 { 01980 std::__heap_select(__first, __nth + 1, __last, __comp); 01981 // Place the nth largest element in its final position. 01982 std::iter_swap(__first, __nth); 01983 return; 01984 } 01985 --__depth_limit; 01986 _RandomAccessIterator __cut = 01987 std::__unguarded_partition_pivot(__first, __last, __comp); 01988 if (__cut <= __nth) 01989 __first = __cut; 01990 else 01991 __last = __cut; 01992 } 01993 std::__insertion_sort(__first, __last, __comp); 01994 } 01995 01996 // nth_element 01997 01998 // lower_bound moved to stl_algobase.h 01999 02000 /** 02001 * @brief Finds the first position in which @p __val could be inserted 02002 * without changing the ordering. 02003 * @ingroup binary_search_algorithms 02004 * @param __first An iterator. 02005 * @param __last Another iterator. 02006 * @param __val The search term. 02007 * @param __comp A functor to use for comparisons. 02008 * @return An iterator pointing to the first element <em>not less 02009 * than</em> @p __val, or end() if every element is less 02010 * than @p __val. 02011 * @ingroup binary_search_algorithms 02012 * 02013 * The comparison function should have the same effects on ordering as 02014 * the function used for the initial sort. 02015 */ 02016 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02017 inline _ForwardIterator 02018 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 02019 const _Tp& __val, _Compare __comp) 02020 { 02021 typedef typename iterator_traits<_ForwardIterator>::value_type 02022 _ValueType; 02023 02024 // concept requirements 02025 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02026 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02027 _ValueType, _Tp>) 02028 __glibcxx_requires_partitioned_lower_pred(__first, __last, 02029 __val, __comp); 02030 02031 return std::__lower_bound(__first, __last, __val, 02032 __gnu_cxx::__ops::__iter_comp_val(__comp)); 02033 } 02034 02035 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02036 _ForwardIterator 02037 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02038 const _Tp& __val, _Compare __comp) 02039 { 02040 typedef typename iterator_traits<_ForwardIterator>::difference_type 02041 _DistanceType; 02042 02043 _DistanceType __len = std::distance(__first, __last); 02044 02045 while (__len > 0) 02046 { 02047 _DistanceType __half = __len >> 1; 02048 _ForwardIterator __middle = __first; 02049 std::advance(__middle, __half); 02050 if (__comp(__val, __middle)) 02051 __len = __half; 02052 else 02053 { 02054 __first = __middle; 02055 ++__first; 02056 __len = __len - __half - 1; 02057 } 02058 } 02059 return __first; 02060 } 02061 02062 /** 02063 * @brief Finds the last position in which @p __val could be inserted 02064 * without changing the ordering. 02065 * @ingroup binary_search_algorithms 02066 * @param __first An iterator. 02067 * @param __last Another iterator. 02068 * @param __val The search term. 02069 * @return An iterator pointing to the first element greater than @p __val, 02070 * or end() if no elements are greater than @p __val. 02071 * @ingroup binary_search_algorithms 02072 */ 02073 template<typename _ForwardIterator, typename _Tp> 02074 inline _ForwardIterator 02075 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02076 const _Tp& __val) 02077 { 02078 typedef typename iterator_traits<_ForwardIterator>::value_type 02079 _ValueType; 02080 02081 // concept requirements 02082 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02083 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) 02084 __glibcxx_requires_partitioned_upper(__first, __last, __val); 02085 02086 return std::__upper_bound(__first, __last, __val, 02087 __gnu_cxx::__ops::__val_less_iter()); 02088 } 02089 02090 /** 02091 * @brief Finds the last position in which @p __val could be inserted 02092 * without changing the ordering. 02093 * @ingroup binary_search_algorithms 02094 * @param __first An iterator. 02095 * @param __last Another iterator. 02096 * @param __val The search term. 02097 * @param __comp A functor to use for comparisons. 02098 * @return An iterator pointing to the first element greater than @p __val, 02099 * or end() if no elements are greater than @p __val. 02100 * @ingroup binary_search_algorithms 02101 * 02102 * The comparison function should have the same effects on ordering as 02103 * the function used for the initial sort. 02104 */ 02105 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02106 inline _ForwardIterator 02107 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02108 const _Tp& __val, _Compare __comp) 02109 { 02110 typedef typename iterator_traits<_ForwardIterator>::value_type 02111 _ValueType; 02112 02113 // concept requirements 02114 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02115 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02116 _Tp, _ValueType>) 02117 __glibcxx_requires_partitioned_upper_pred(__first, __last, 02118 __val, __comp); 02119 02120 return std::__upper_bound(__first, __last, __val, 02121 __gnu_cxx::__ops::__val_comp_iter(__comp)); 02122 } 02123 02124 template<typename _ForwardIterator, typename _Tp, 02125 typename _CompareItTp, typename _CompareTpIt> 02126 pair<_ForwardIterator, _ForwardIterator> 02127 __equal_range(_ForwardIterator __first, _ForwardIterator __last, 02128 const _Tp& __val, 02129 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it) 02130 { 02131 typedef typename iterator_traits<_ForwardIterator>::difference_type 02132 _DistanceType; 02133 02134 _DistanceType __len = std::distance(__first, __last); 02135 02136 while (__len > 0) 02137 { 02138 _DistanceType __half = __len >> 1; 02139 _ForwardIterator __middle = __first; 02140 std::advance(__middle, __half); 02141 if (__comp_it_val(__middle, __val)) 02142 { 02143 __first = __middle; 02144 ++__first; 02145 __len = __len - __half - 1; 02146 } 02147 else if (__comp_val_it(__val, __middle)) 02148 __len = __half; 02149 else 02150 { 02151 _ForwardIterator __left 02152 = std::__lower_bound(__first, __middle, __val, __comp_it_val); 02153 std::advance(__first, __len); 02154 _ForwardIterator __right 02155 = std::__upper_bound(++__middle, __first, __val, __comp_val_it); 02156 return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 02157 } 02158 } 02159 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 02160 } 02161 02162 /** 02163 * @brief Finds the largest subrange in which @p __val could be inserted 02164 * at any place in it without changing the ordering. 02165 * @ingroup binary_search_algorithms 02166 * @param __first An iterator. 02167 * @param __last Another iterator. 02168 * @param __val The search term. 02169 * @return An pair of iterators defining the subrange. 02170 * @ingroup binary_search_algorithms 02171 * 02172 * This is equivalent to 02173 * @code 02174 * std::make_pair(lower_bound(__first, __last, __val), 02175 * upper_bound(__first, __last, __val)) 02176 * @endcode 02177 * but does not actually call those functions. 02178 */ 02179 template<typename _ForwardIterator, typename _Tp> 02180 inline pair<_ForwardIterator, _ForwardIterator> 02181 equal_range(_ForwardIterator __first, _ForwardIterator __last, 02182 const _Tp& __val) 02183 { 02184 typedef typename iterator_traits<_ForwardIterator>::value_type 02185 _ValueType; 02186 02187 // concept requirements 02188 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02189 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) 02190 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) 02191 __glibcxx_requires_partitioned_lower(__first, __last, __val); 02192 __glibcxx_requires_partitioned_upper(__first, __last, __val); 02193 02194 return std::__equal_range(__first, __last, __val, 02195 __gnu_cxx::__ops::__iter_less_val(), 02196 __gnu_cxx::__ops::__val_less_iter()); 02197 } 02198 02199 /** 02200 * @brief Finds the largest subrange in which @p __val could be inserted 02201 * at any place in it without changing the ordering. 02202 * @param __first An iterator. 02203 * @param __last Another iterator. 02204 * @param __val The search term. 02205 * @param __comp A functor to use for comparisons. 02206 * @return An pair of iterators defining the subrange. 02207 * @ingroup binary_search_algorithms 02208 * 02209 * This is equivalent to 02210 * @code 02211 * std::make_pair(lower_bound(__first, __last, __val, __comp), 02212 * upper_bound(__first, __last, __val, __comp)) 02213 * @endcode 02214 * but does not actually call those functions. 02215 */ 02216 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02217 inline pair<_ForwardIterator, _ForwardIterator> 02218 equal_range(_ForwardIterator __first, _ForwardIterator __last, 02219 const _Tp& __val, _Compare __comp) 02220 { 02221 typedef typename iterator_traits<_ForwardIterator>::value_type 02222 _ValueType; 02223 02224 // concept requirements 02225 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02226 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02227 _ValueType, _Tp>) 02228 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02229 _Tp, _ValueType>) 02230 __glibcxx_requires_partitioned_lower_pred(__first, __last, 02231 __val, __comp); 02232 __glibcxx_requires_partitioned_upper_pred(__first, __last, 02233 __val, __comp); 02234 02235 return std::__equal_range(__first, __last, __val, 02236 __gnu_cxx::__ops::__iter_comp_val(__comp), 02237 __gnu_cxx::__ops::__val_comp_iter(__comp)); 02238 } 02239 02240 /** 02241 * @brief Determines whether an element exists in a range. 02242 * @ingroup binary_search_algorithms 02243 * @param __first An iterator. 02244 * @param __last Another iterator. 02245 * @param __val The search term. 02246 * @return True if @p __val (or its equivalent) is in [@p 02247 * __first,@p __last ]. 02248 * 02249 * Note that this does not actually return an iterator to @p __val. For 02250 * that, use std::find or a container's specialized find member functions. 02251 */ 02252 template<typename _ForwardIterator, typename _Tp> 02253 bool 02254 binary_search(_ForwardIterator __first, _ForwardIterator __last, 02255 const _Tp& __val) 02256 { 02257 typedef typename iterator_traits<_ForwardIterator>::value_type 02258 _ValueType; 02259 02260 // concept requirements 02261 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02262 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) 02263 __glibcxx_requires_partitioned_lower(__first, __last, __val); 02264 __glibcxx_requires_partitioned_upper(__first, __last, __val); 02265 02266 _ForwardIterator __i 02267 = std::__lower_bound(__first, __last, __val, 02268 __gnu_cxx::__ops::__iter_less_val()); 02269 return __i != __last && !(__val < *__i); 02270 } 02271 02272 /** 02273 * @brief Determines whether an element exists in a range. 02274 * @ingroup binary_search_algorithms 02275 * @param __first An iterator. 02276 * @param __last Another iterator. 02277 * @param __val The search term. 02278 * @param __comp A functor to use for comparisons. 02279 * @return True if @p __val (or its equivalent) is in @p [__first,__last]. 02280 * 02281 * Note that this does not actually return an iterator to @p __val. For 02282 * that, use std::find or a container's specialized find member functions. 02283 * 02284 * The comparison function should have the same effects on ordering as 02285 * the function used for the initial sort. 02286 */ 02287 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02288 bool 02289 binary_search(_ForwardIterator __first, _ForwardIterator __last, 02290 const _Tp& __val, _Compare __comp) 02291 { 02292 typedef typename iterator_traits<_ForwardIterator>::value_type 02293 _ValueType; 02294 02295 // concept requirements 02296 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02297 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02298 _Tp, _ValueType>) 02299 __glibcxx_requires_partitioned_lower_pred(__first, __last, 02300 __val, __comp); 02301 __glibcxx_requires_partitioned_upper_pred(__first, __last, 02302 __val, __comp); 02303 02304 _ForwardIterator __i 02305 = std::__lower_bound(__first, __last, __val, 02306 __gnu_cxx::__ops::__iter_comp_val(__comp)); 02307 return __i != __last && !bool(__comp(__val, *__i)); 02308 } 02309 02310 // merge 02311 02312 /// This is a helper function for the __merge_adaptive routines. 02313 template<typename _InputIterator1, typename _InputIterator2, 02314 typename _OutputIterator, typename _Compare> 02315 void 02316 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, 02317 _InputIterator2 __first2, _InputIterator2 __last2, 02318 _OutputIterator __result, _Compare __comp) 02319 { 02320 while (__first1 != __last1 && __first2 != __last2) 02321 { 02322 if (__comp(__first2, __first1)) 02323 { 02324 *__result = _GLIBCXX_MOVE(*__first2); 02325 ++__first2; 02326 } 02327 else 02328 { 02329 *__result = _GLIBCXX_MOVE(*__first1); 02330 ++__first1; 02331 } 02332 ++__result; 02333 } 02334 if (__first1 != __last1) 02335 _GLIBCXX_MOVE3(__first1, __last1, __result); 02336 } 02337 02338 /// This is a helper function for the __merge_adaptive routines. 02339 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 02340 typename _BidirectionalIterator3, typename _Compare> 02341 void 02342 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, 02343 _BidirectionalIterator1 __last1, 02344 _BidirectionalIterator2 __first2, 02345 _BidirectionalIterator2 __last2, 02346 _BidirectionalIterator3 __result, 02347 _Compare __comp) 02348 { 02349 if (__first1 == __last1) 02350 { 02351 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); 02352 return; 02353 } 02354 else if (__first2 == __last2) 02355 return; 02356 02357 --__last1; 02358 --__last2; 02359 while (true) 02360 { 02361 if (__comp(__last2, __last1)) 02362 { 02363 *--__result = _GLIBCXX_MOVE(*__last1); 02364 if (__first1 == __last1) 02365 { 02366 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); 02367 return; 02368 } 02369 --__last1; 02370 } 02371 else 02372 { 02373 *--__result = _GLIBCXX_MOVE(*__last2); 02374 if (__first2 == __last2) 02375 return; 02376 --__last2; 02377 } 02378 } 02379 } 02380 02381 /// This is a helper function for the merge routines. 02382 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 02383 typename _Distance> 02384 _BidirectionalIterator1 02385 __rotate_adaptive(_BidirectionalIterator1 __first, 02386 _BidirectionalIterator1 __middle, 02387 _BidirectionalIterator1 __last, 02388 _Distance __len1, _Distance __len2, 02389 _BidirectionalIterator2 __buffer, 02390 _Distance __buffer_size) 02391 { 02392 _BidirectionalIterator2 __buffer_end; 02393 if (__len1 > __len2 && __len2 <= __buffer_size) 02394 { 02395 if (__len2) 02396 { 02397 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 02398 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last); 02399 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first); 02400 } 02401 else 02402 return __first; 02403 } 02404 else if (__len1 <= __buffer_size) 02405 { 02406 if (__len1) 02407 { 02408 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 02409 _GLIBCXX_MOVE3(__middle, __last, __first); 02410 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last); 02411 } 02412 else 02413 return __last; 02414 } 02415 else 02416 { 02417 std::rotate(__first, __middle, __last); 02418 std::advance(__first, std::distance(__middle, __last)); 02419 return __first; 02420 } 02421 } 02422 02423 /// This is a helper function for the merge routines. 02424 template<typename _BidirectionalIterator, typename _Distance, 02425 typename _Pointer, typename _Compare> 02426 void 02427 __merge_adaptive(_BidirectionalIterator __first, 02428 _BidirectionalIterator __middle, 02429 _BidirectionalIterator __last, 02430 _Distance __len1, _Distance __len2, 02431 _Pointer __buffer, _Distance __buffer_size, 02432 _Compare __comp) 02433 { 02434 if (__len1 <= __len2 && __len1 <= __buffer_size) 02435 { 02436 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 02437 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, 02438 __first, __comp); 02439 } 02440 else if (__len2 <= __buffer_size) 02441 { 02442 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 02443 std::__move_merge_adaptive_backward(__first, __middle, __buffer, 02444 __buffer_end, __last, __comp); 02445 } 02446 else 02447 { 02448 _BidirectionalIterator __first_cut = __first; 02449 _BidirectionalIterator __second_cut = __middle; 02450 _Distance __len11 = 0; 02451 _Distance __len22 = 0; 02452 if (__len1 > __len2) 02453 { 02454 __len11 = __len1 / 2; 02455 std::advance(__first_cut, __len11); 02456 __second_cut 02457 = std::__lower_bound(__middle, __last, *__first_cut, 02458 __gnu_cxx::__ops::__iter_comp_val(__comp)); 02459 __len22 = std::distance(__middle, __second_cut); 02460 } 02461 else 02462 { 02463 __len22 = __len2 / 2; 02464 std::advance(__second_cut, __len22); 02465 __first_cut 02466 = std::__upper_bound(__first, __middle, *__second_cut, 02467 __gnu_cxx::__ops::__val_comp_iter(__comp)); 02468 __len11 = std::distance(__first, __first_cut); 02469 } 02470 02471 _BidirectionalIterator __new_middle 02472 = std::__rotate_adaptive(__first_cut, __middle, __second_cut, 02473 __len1 - __len11, __len22, __buffer, 02474 __buffer_size); 02475 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 02476 __len22, __buffer, __buffer_size, __comp); 02477 std::__merge_adaptive(__new_middle, __second_cut, __last, 02478 __len1 - __len11, 02479 __len2 - __len22, __buffer, 02480 __buffer_size, __comp); 02481 } 02482 } 02483 02484 /// This is a helper function for the merge routines. 02485 template<typename _BidirectionalIterator, typename _Distance, 02486 typename _Compare> 02487 void 02488 __merge_without_buffer(_BidirectionalIterator __first, 02489 _BidirectionalIterator __middle, 02490 _BidirectionalIterator __last, 02491 _Distance __len1, _Distance __len2, 02492 _Compare __comp) 02493 { 02494 if (__len1 == 0 || __len2 == 0) 02495 return; 02496 02497 if (__len1 + __len2 == 2) 02498 { 02499 if (__comp(__middle, __first)) 02500 std::iter_swap(__first, __middle); 02501 return; 02502 } 02503 02504 _BidirectionalIterator __first_cut = __first; 02505 _BidirectionalIterator __second_cut = __middle; 02506 _Distance __len11 = 0; 02507 _Distance __len22 = 0; 02508 if (__len1 > __len2) 02509 { 02510 __len11 = __len1 / 2; 02511 std::advance(__first_cut, __len11); 02512 __second_cut 02513 = std::__lower_bound(__middle, __last, *__first_cut, 02514 __gnu_cxx::__ops::__iter_comp_val(__comp)); 02515 __len22 = std::distance(__middle, __second_cut); 02516 } 02517 else 02518 { 02519 __len22 = __len2 / 2; 02520 std::advance(__second_cut, __len22); 02521 __first_cut 02522 = std::__upper_bound(__first, __middle, *__second_cut, 02523 __gnu_cxx::__ops::__val_comp_iter(__comp)); 02524 __len11 = std::distance(__first, __first_cut); 02525 } 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 _GLIBCXX14_CONSTEXPR 03298 inline pair<const _Tp&, const _Tp&> 03299 minmax(const _Tp& __a, const _Tp& __b) 03300 { 03301 // concept requirements 03302 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 03303 03304 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a) 03305 : pair<const _Tp&, const _Tp&>(__a, __b); 03306 } 03307 03308 /** 03309 * @brief Determines min and max at once as an ordered pair. 03310 * @ingroup sorting_algorithms 03311 * @param __a A thing of arbitrary type. 03312 * @param __b Another thing of arbitrary type. 03313 * @param __comp A @link comparison_functors comparison functor @endlink. 03314 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a, 03315 * __b) otherwise. 03316 */ 03317 template<typename _Tp, typename _Compare> 03318 _GLIBCXX14_CONSTEXPR 03319 inline pair<const _Tp&, const _Tp&> 03320 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) 03321 { 03322 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) 03323 : pair<const _Tp&, const _Tp&>(__a, __b); 03324 } 03325 03326 template<typename _ForwardIterator, typename _Compare> 03327 _GLIBCXX14_CONSTEXPR 03328 pair<_ForwardIterator, _ForwardIterator> 03329 __minmax_element(_ForwardIterator __first, _ForwardIterator __last, 03330 _Compare __comp) 03331 { 03332 _ForwardIterator __next = __first; 03333 if (__first == __last 03334 || ++__next == __last) 03335 return std::make_pair(__first, __first); 03336 03337 _ForwardIterator __min{}, __max{}; 03338 if (__comp(__next, __first)) 03339 { 03340 __min = __next; 03341 __max = __first; 03342 } 03343 else 03344 { 03345 __min = __first; 03346 __max = __next; 03347 } 03348 03349 __first = __next; 03350 ++__first; 03351 03352 while (__first != __last) 03353 { 03354 __next = __first; 03355 if (++__next == __last) 03356 { 03357 if (__comp(__first, __min)) 03358 __min = __first; 03359 else if (!__comp(__first, __max)) 03360 __max = __first; 03361 break; 03362 } 03363 03364 if (__comp(__next, __first)) 03365 { 03366 if (__comp(__next, __min)) 03367 __min = __next; 03368 if (!__comp(__first, __max)) 03369 __max = __first; 03370 } 03371 else 03372 { 03373 if (__comp(__first, __min)) 03374 __min = __first; 03375 if (!__comp(__next, __max)) 03376 __max = __next; 03377 } 03378 03379 __first = __next; 03380 ++__first; 03381 } 03382 03383 return std::make_pair(__min, __max); 03384 } 03385 03386 /** 03387 * @brief Return a pair of iterators pointing to the minimum and maximum 03388 * elements in a range. 03389 * @ingroup sorting_algorithms 03390 * @param __first Start of range. 03391 * @param __last End of range. 03392 * @return make_pair(m, M), where m is the first iterator i in 03393 * [__first, __last) such that no other element in the range is 03394 * smaller, and where M is the last iterator i in [__first, __last) 03395 * such that no other element in the range is larger. 03396 */ 03397 template<typename _ForwardIterator> 03398 _GLIBCXX14_CONSTEXPR 03399 inline pair<_ForwardIterator, _ForwardIterator> 03400 minmax_element(_ForwardIterator __first, _ForwardIterator __last) 03401 { 03402 // concept requirements 03403 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03404 __glibcxx_function_requires(_LessThanComparableConcept< 03405 typename iterator_traits<_ForwardIterator>::value_type>) 03406 __glibcxx_requires_valid_range(__first, __last); 03407 03408 return std::__minmax_element(__first, __last, 03409 __gnu_cxx::__ops::__iter_less_iter()); 03410 } 03411 03412 /** 03413 * @brief Return a pair of iterators pointing to the minimum and maximum 03414 * elements in a range. 03415 * @ingroup sorting_algorithms 03416 * @param __first Start of range. 03417 * @param __last End of range. 03418 * @param __comp Comparison functor. 03419 * @return make_pair(m, M), where m is the first iterator i in 03420 * [__first, __last) such that no other element in the range is 03421 * smaller, and where M is the last iterator i in [__first, __last) 03422 * such that no other element in the range is larger. 03423 */ 03424 template<typename _ForwardIterator, typename _Compare> 03425 _GLIBCXX14_CONSTEXPR 03426 inline pair<_ForwardIterator, _ForwardIterator> 03427 minmax_element(_ForwardIterator __first, _ForwardIterator __last, 03428 _Compare __comp) 03429 { 03430 // concept requirements 03431 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03432 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03433 typename iterator_traits<_ForwardIterator>::value_type, 03434 typename iterator_traits<_ForwardIterator>::value_type>) 03435 __glibcxx_requires_valid_range(__first, __last); 03436 03437 return std::__minmax_element(__first, __last, 03438 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 03439 } 03440 03441 // N2722 + DR 915. 03442 template<typename _Tp> 03443 _GLIBCXX14_CONSTEXPR 03444 inline _Tp 03445 min(initializer_list<_Tp> __l) 03446 { return *std::min_element(__l.begin(), __l.end()); } 03447 03448 template<typename _Tp, typename _Compare> 03449 _GLIBCXX14_CONSTEXPR 03450 inline _Tp 03451 min(initializer_list<_Tp> __l, _Compare __comp) 03452 { return *std::min_element(__l.begin(), __l.end(), __comp); } 03453 03454 template<typename _Tp> 03455 _GLIBCXX14_CONSTEXPR 03456 inline _Tp 03457 max(initializer_list<_Tp> __l) 03458 { return *std::max_element(__l.begin(), __l.end()); } 03459 03460 template<typename _Tp, typename _Compare> 03461 _GLIBCXX14_CONSTEXPR 03462 inline _Tp 03463 max(initializer_list<_Tp> __l, _Compare __comp) 03464 { return *std::max_element(__l.begin(), __l.end(), __comp); } 03465 03466 template<typename _Tp> 03467 _GLIBCXX14_CONSTEXPR 03468 inline pair<_Tp, _Tp> 03469 minmax(initializer_list<_Tp> __l) 03470 { 03471 pair<const _Tp*, const _Tp*> __p = 03472 std::minmax_element(__l.begin(), __l.end()); 03473 return std::make_pair(*__p.first, *__p.second); 03474 } 03475 03476 template<typename _Tp, typename _Compare> 03477 _GLIBCXX14_CONSTEXPR 03478 inline pair<_Tp, _Tp> 03479 minmax(initializer_list<_Tp> __l, _Compare __comp) 03480 { 03481 pair<const _Tp*, const _Tp*> __p = 03482 std::minmax_element(__l.begin(), __l.end(), __comp); 03483 return std::make_pair(*__p.first, *__p.second); 03484 } 03485 03486 template<typename _ForwardIterator1, typename _ForwardIterator2, 03487 typename _BinaryPredicate> 03488 bool 03489 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03490 _ForwardIterator2 __first2, _BinaryPredicate __pred) 03491 { 03492 // Efficiently compare identical prefixes: O(N) if sequences 03493 // have the same elements in the same order. 03494 for (; __first1 != __last1; ++__first1, ++__first2) 03495 if (!__pred(__first1, __first2)) 03496 break; 03497 03498 if (__first1 == __last1) 03499 return true; 03500 03501 // Establish __last2 assuming equal ranges by iterating over the 03502 // rest of the list. 03503 _ForwardIterator2 __last2 = __first2; 03504 std::advance(__last2, std::distance(__first1, __last1)); 03505 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 03506 { 03507 if (__scan != std::__find_if(__first1, __scan, 03508 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 03509 continue; // We've seen this one before. 03510 03511 auto __matches 03512 = std::__count_if(__first2, __last2, 03513 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 03514 if (0 == __matches || 03515 std::__count_if(__scan, __last1, 03516 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 03517 != __matches) 03518 return false; 03519 } 03520 return true; 03521 } 03522 03523 /** 03524 * @brief Checks whether a permutation of the second sequence is equal 03525 * to the first sequence. 03526 * @ingroup non_mutating_algorithms 03527 * @param __first1 Start of first range. 03528 * @param __last1 End of first range. 03529 * @param __first2 Start of second range. 03530 * @return true if there exists a permutation of the elements in the range 03531 * [__first2, __first2 + (__last1 - __first1)), beginning with 03532 * ForwardIterator2 begin, such that equal(__first1, __last1, begin) 03533 * returns true; otherwise, returns false. 03534 */ 03535 template<typename _ForwardIterator1, typename _ForwardIterator2> 03536 inline bool 03537 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03538 _ForwardIterator2 __first2) 03539 { 03540 // concept requirements 03541 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 03542 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 03543 __glibcxx_function_requires(_EqualOpConcept< 03544 typename iterator_traits<_ForwardIterator1>::value_type, 03545 typename iterator_traits<_ForwardIterator2>::value_type>) 03546 __glibcxx_requires_valid_range(__first1, __last1); 03547 03548 return std::__is_permutation(__first1, __last1, __first2, 03549 __gnu_cxx::__ops::__iter_equal_to_iter()); 03550 } 03551 03552 /** 03553 * @brief Checks whether a permutation of the second sequence is equal 03554 * to the first sequence. 03555 * @ingroup non_mutating_algorithms 03556 * @param __first1 Start of first range. 03557 * @param __last1 End of first range. 03558 * @param __first2 Start of second range. 03559 * @param __pred A binary predicate. 03560 * @return true if there exists a permutation of the elements in 03561 * the range [__first2, __first2 + (__last1 - __first1)), 03562 * beginning with ForwardIterator2 begin, such that 03563 * equal(__first1, __last1, __begin, __pred) returns true; 03564 * otherwise, returns false. 03565 */ 03566 template<typename _ForwardIterator1, typename _ForwardIterator2, 03567 typename _BinaryPredicate> 03568 inline bool 03569 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03570 _ForwardIterator2 __first2, _BinaryPredicate __pred) 03571 { 03572 // concept requirements 03573 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 03574 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 03575 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 03576 typename iterator_traits<_ForwardIterator1>::value_type, 03577 typename iterator_traits<_ForwardIterator2>::value_type>) 03578 __glibcxx_requires_valid_range(__first1, __last1); 03579 03580 return std::__is_permutation(__first1, __last1, __first2, 03581 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 03582 } 03583 03584 #if __cplusplus > 201103L 03585 template<typename _ForwardIterator1, typename _ForwardIterator2, 03586 typename _BinaryPredicate> 03587 bool 03588 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03589 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 03590 _BinaryPredicate __pred) 03591 { 03592 using _Cat1 03593 = typename iterator_traits<_ForwardIterator1>::iterator_category; 03594 using _Cat2 03595 = typename iterator_traits<_ForwardIterator2>::iterator_category; 03596 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>; 03597 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>; 03598 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA(); 03599 if (__ra_iters) 03600 { 03601 auto __d1 = std::distance(__first1, __last1); 03602 auto __d2 = std::distance(__first2, __last2); 03603 if (__d1 != __d2) 03604 return false; 03605 } 03606 03607 // Efficiently compare identical prefixes: O(N) if sequences 03608 // have the same elements in the same order. 03609 for (; __first1 != __last1 && __first2 != __last2; 03610 ++__first1, ++__first2) 03611 if (!__pred(__first1, __first2)) 03612 break; 03613 03614 if (__ra_iters) 03615 { 03616 if (__first1 == __last1) 03617 return true; 03618 } 03619 else 03620 { 03621 auto __d1 = std::distance(__first1, __last1); 03622 auto __d2 = std::distance(__first2, __last2); 03623 if (__d1 == 0 && __d2 == 0) 03624 return true; 03625 if (__d1 != __d2) 03626 return false; 03627 } 03628 03629 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 03630 { 03631 if (__scan != std::__find_if(__first1, __scan, 03632 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 03633 continue; // We've seen this one before. 03634 03635 auto __matches = std::__count_if(__first2, __last2, 03636 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 03637 if (0 == __matches 03638 || std::__count_if(__scan, __last1, 03639 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 03640 != __matches) 03641 return false; 03642 } 03643 return true; 03644 } 03645 03646 /** 03647 * @brief Checks whether a permutaion of the second sequence is equal 03648 * to the first sequence. 03649 * @ingroup non_mutating_algorithms 03650 * @param __first1 Start of first range. 03651 * @param __last1 End of first range. 03652 * @param __first2 Start of second range. 03653 * @param __last2 End of first range. 03654 * @return true if there exists a permutation of the elements in the range 03655 * [__first2, __last2), beginning with ForwardIterator2 begin, 03656 * such that equal(__first1, __last1, begin) returns true; 03657 * otherwise, returns false. 03658 */ 03659 template<typename _ForwardIterator1, typename _ForwardIterator2> 03660 inline bool 03661 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03662 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 03663 { 03664 __glibcxx_requires_valid_range(__first1, __last1); 03665 __glibcxx_requires_valid_range(__first2, __last2); 03666 03667 return 03668 std::__is_permutation(__first1, __last1, __first2, __last2, 03669 __gnu_cxx::__ops::__iter_equal_to_iter()); 03670 } 03671 03672 /** 03673 * @brief Checks whether a permutation of the second sequence is equal 03674 * to the first sequence. 03675 * @ingroup non_mutating_algorithms 03676 * @param __first1 Start of first range. 03677 * @param __last1 End of first range. 03678 * @param __first2 Start of second range. 03679 * @param __last2 End of first range. 03680 * @param __pred A binary predicate. 03681 * @return true if there exists a permutation of the elements in the range 03682 * [__first2, __last2), beginning with ForwardIterator2 begin, 03683 * such that equal(__first1, __last1, __begin, __pred) returns true; 03684 * otherwise, returns false. 03685 */ 03686 template<typename _ForwardIterator1, typename _ForwardIterator2, 03687 typename _BinaryPredicate> 03688 inline bool 03689 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03690 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 03691 _BinaryPredicate __pred) 03692 { 03693 __glibcxx_requires_valid_range(__first1, __last1); 03694 __glibcxx_requires_valid_range(__first2, __last2); 03695 03696 return std::__is_permutation(__first1, __last1, __first2, __last2, 03697 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 03698 } 03699 #endif 03700 03701 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 03702 /** 03703 * @brief Shuffle the elements of a sequence using a uniform random 03704 * number generator. 03705 * @ingroup mutating_algorithms 03706 * @param __first A forward iterator. 03707 * @param __last A forward iterator. 03708 * @param __g A UniformRandomNumberGenerator (26.5.1.3). 03709 * @return Nothing. 03710 * 03711 * Reorders the elements in the range @p [__first,__last) using @p __g to 03712 * provide random numbers. 03713 */ 03714 template<typename _RandomAccessIterator, 03715 typename _UniformRandomNumberGenerator> 03716 void 03717 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 03718 _UniformRandomNumberGenerator&& __g) 03719 { 03720 // concept requirements 03721 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 03722 _RandomAccessIterator>) 03723 __glibcxx_requires_valid_range(__first, __last); 03724 03725 if (__first == __last) 03726 return; 03727 03728 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 03729 _DistanceType; 03730 03731 typedef typename std::make_unsigned<_DistanceType>::type __ud_type; 03732 typedef typename std::uniform_int_distribution<__ud_type> __distr_type; 03733 typedef typename __distr_type::param_type __p_type; 03734 __distr_type __d; 03735 03736 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 03737 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first))); 03738 } 03739 #endif 03740 03741 #endif // C++11 03742 03743 _GLIBCXX_END_NAMESPACE_VERSION 03744 03745 _GLIBCXX_BEGIN_NAMESPACE_ALGO 03746 03747 /** 03748 * @brief Apply a function to every element of a sequence. 03749 * @ingroup non_mutating_algorithms 03750 * @param __first An input iterator. 03751 * @param __last An input iterator. 03752 * @param __f A unary function object. 03753 * @return @p __f (std::move(@p __f) in C++0x). 03754 * 03755 * Applies the function object @p __f to each element in the range 03756 * @p [first,last). @p __f must not modify the order of the sequence. 03757 * If @p __f has a return value it is ignored. 03758 */ 03759 template<typename _InputIterator, typename _Function> 03760 _Function 03761 for_each(_InputIterator __first, _InputIterator __last, _Function __f) 03762 { 03763 // concept requirements 03764 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03765 __glibcxx_requires_valid_range(__first, __last); 03766 for (; __first != __last; ++__first) 03767 __f(*__first); 03768 return _GLIBCXX_MOVE(__f); 03769 } 03770 03771 /** 03772 * @brief Find the first occurrence of a value in a sequence. 03773 * @ingroup non_mutating_algorithms 03774 * @param __first An input iterator. 03775 * @param __last An input iterator. 03776 * @param __val The value to find. 03777 * @return The first iterator @c i in the range @p [__first,__last) 03778 * such that @c *i == @p __val, or @p __last if no such iterator exists. 03779 */ 03780 template<typename _InputIterator, typename _Tp> 03781 inline _InputIterator 03782 find(_InputIterator __first, _InputIterator __last, 03783 const _Tp& __val) 03784 { 03785 // concept requirements 03786 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03787 __glibcxx_function_requires(_EqualOpConcept< 03788 typename iterator_traits<_InputIterator>::value_type, _Tp>) 03789 __glibcxx_requires_valid_range(__first, __last); 03790 return std::__find_if(__first, __last, 03791 __gnu_cxx::__ops::__iter_equals_val(__val)); 03792 } 03793 03794 /** 03795 * @brief Find the first element in a sequence for which a 03796 * predicate is true. 03797 * @ingroup non_mutating_algorithms 03798 * @param __first An input iterator. 03799 * @param __last An input iterator. 03800 * @param __pred A predicate. 03801 * @return The first iterator @c i in the range @p [__first,__last) 03802 * such that @p __pred(*i) is true, or @p __last if no such iterator exists. 03803 */ 03804 template<typename _InputIterator, typename _Predicate> 03805 inline _InputIterator 03806 find_if(_InputIterator __first, _InputIterator __last, 03807 _Predicate __pred) 03808 { 03809 // concept requirements 03810 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03811 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 03812 typename iterator_traits<_InputIterator>::value_type>) 03813 __glibcxx_requires_valid_range(__first, __last); 03814 03815 return std::__find_if(__first, __last, 03816 __gnu_cxx::__ops::__pred_iter(__pred)); 03817 } 03818 03819 /** 03820 * @brief Find element from a set in a sequence. 03821 * @ingroup non_mutating_algorithms 03822 * @param __first1 Start of range to search. 03823 * @param __last1 End of range to search. 03824 * @param __first2 Start of match candidates. 03825 * @param __last2 End of match candidates. 03826 * @return The first iterator @c i in the range 03827 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an 03828 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists. 03829 * 03830 * Searches the range @p [__first1,__last1) for an element that is 03831 * equal to some element in the range [__first2,__last2). If 03832 * found, returns an iterator in the range [__first1,__last1), 03833 * otherwise returns @p __last1. 03834 */ 03835 template<typename _InputIterator, typename _ForwardIterator> 03836 _InputIterator 03837 find_first_of(_InputIterator __first1, _InputIterator __last1, 03838 _ForwardIterator __first2, _ForwardIterator __last2) 03839 { 03840 // concept requirements 03841 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03842 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03843 __glibcxx_function_requires(_EqualOpConcept< 03844 typename iterator_traits<_InputIterator>::value_type, 03845 typename iterator_traits<_ForwardIterator>::value_type>) 03846 __glibcxx_requires_valid_range(__first1, __last1); 03847 __glibcxx_requires_valid_range(__first2, __last2); 03848 03849 for (; __first1 != __last1; ++__first1) 03850 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 03851 if (*__first1 == *__iter) 03852 return __first1; 03853 return __last1; 03854 } 03855 03856 /** 03857 * @brief Find element from a set in a sequence using a predicate. 03858 * @ingroup non_mutating_algorithms 03859 * @param __first1 Start of range to search. 03860 * @param __last1 End of range to search. 03861 * @param __first2 Start of match candidates. 03862 * @param __last2 End of match candidates. 03863 * @param __comp Predicate to use. 03864 * @return The first iterator @c i in the range 03865 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true 03866 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no 03867 * such iterator exists. 03868 * 03869 03870 * Searches the range @p [__first1,__last1) for an element that is 03871 * equal to some element in the range [__first2,__last2). If 03872 * found, returns an iterator in the range [__first1,__last1), 03873 * otherwise returns @p __last1. 03874 */ 03875 template<typename _InputIterator, typename _ForwardIterator, 03876 typename _BinaryPredicate> 03877 _InputIterator 03878 find_first_of(_InputIterator __first1, _InputIterator __last1, 03879 _ForwardIterator __first2, _ForwardIterator __last2, 03880 _BinaryPredicate __comp) 03881 { 03882 // concept requirements 03883 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03884 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03885 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 03886 typename iterator_traits<_InputIterator>::value_type, 03887 typename iterator_traits<_ForwardIterator>::value_type>) 03888 __glibcxx_requires_valid_range(__first1, __last1); 03889 __glibcxx_requires_valid_range(__first2, __last2); 03890 03891 for (; __first1 != __last1; ++__first1) 03892 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 03893 if (__comp(*__first1, *__iter)) 03894 return __first1; 03895 return __last1; 03896 } 03897 03898 /** 03899 * @brief Find two adjacent values in a sequence that are equal. 03900 * @ingroup non_mutating_algorithms 03901 * @param __first A forward iterator. 03902 * @param __last A forward iterator. 03903 * @return The first iterator @c i such that @c i and @c i+1 are both 03904 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1), 03905 * or @p __last if no such iterator exists. 03906 */ 03907 template<typename _ForwardIterator> 03908 inline _ForwardIterator 03909 adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 03910 { 03911 // concept requirements 03912 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03913 __glibcxx_function_requires(_EqualityComparableConcept< 03914 typename iterator_traits<_ForwardIterator>::value_type>) 03915 __glibcxx_requires_valid_range(__first, __last); 03916 03917 return std::__adjacent_find(__first, __last, 03918 __gnu_cxx::__ops::__iter_equal_to_iter()); 03919 } 03920 03921 /** 03922 * @brief Find two adjacent values in a sequence using a predicate. 03923 * @ingroup non_mutating_algorithms 03924 * @param __first A forward iterator. 03925 * @param __last A forward iterator. 03926 * @param __binary_pred A binary predicate. 03927 * @return The first iterator @c i such that @c i and @c i+1 are both 03928 * valid iterators in @p [__first,__last) and such that 03929 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator 03930 * exists. 03931 */ 03932 template<typename _ForwardIterator, typename _BinaryPredicate> 03933 inline _ForwardIterator 03934 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 03935 _BinaryPredicate __binary_pred) 03936 { 03937 // concept requirements 03938 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03939 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 03940 typename iterator_traits<_ForwardIterator>::value_type, 03941 typename iterator_traits<_ForwardIterator>::value_type>) 03942 __glibcxx_requires_valid_range(__first, __last); 03943 03944 return std::__adjacent_find(__first, __last, 03945 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 03946 } 03947 03948 /** 03949 * @brief Count the number of copies of a value in a sequence. 03950 * @ingroup non_mutating_algorithms 03951 * @param __first An input iterator. 03952 * @param __last An input iterator. 03953 * @param __value The value to be counted. 03954 * @return The number of iterators @c i in the range @p [__first,__last) 03955 * for which @c *i == @p __value 03956 */ 03957 template<typename _InputIterator, typename _Tp> 03958 inline typename iterator_traits<_InputIterator>::difference_type 03959 count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 03960 { 03961 // concept requirements 03962 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03963 __glibcxx_function_requires(_EqualOpConcept< 03964 typename iterator_traits<_InputIterator>::value_type, _Tp>) 03965 __glibcxx_requires_valid_range(__first, __last); 03966 03967 return std::__count_if(__first, __last, 03968 __gnu_cxx::__ops::__iter_equals_val(__value)); 03969 } 03970 03971 /** 03972 * @brief Count the elements of a sequence for which a predicate is true. 03973 * @ingroup non_mutating_algorithms 03974 * @param __first An input iterator. 03975 * @param __last An input iterator. 03976 * @param __pred A predicate. 03977 * @return The number of iterators @c i in the range @p [__first,__last) 03978 * for which @p __pred(*i) is true. 03979 */ 03980 template<typename _InputIterator, typename _Predicate> 03981 inline typename iterator_traits<_InputIterator>::difference_type 03982 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 03983 { 03984 // concept requirements 03985 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03986 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 03987 typename iterator_traits<_InputIterator>::value_type>) 03988 __glibcxx_requires_valid_range(__first, __last); 03989 03990 return std::__count_if(__first, __last, 03991 __gnu_cxx::__ops::__pred_iter(__pred)); 03992 } 03993 03994 /** 03995 * @brief Search a sequence for a matching sub-sequence. 03996 * @ingroup non_mutating_algorithms 03997 * @param __first1 A forward iterator. 03998 * @param __last1 A forward iterator. 03999 * @param __first2 A forward iterator. 04000 * @param __last2 A forward iterator. 04001 * @return The first iterator @c i in the range @p 04002 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p 04003 * *(__first2+N) for each @c N in the range @p 04004 * [0,__last2-__first2), or @p __last1 if no such iterator exists. 04005 * 04006 * Searches the range @p [__first1,__last1) for a sub-sequence that 04007 * compares equal value-by-value with the sequence given by @p 04008 * [__first2,__last2) and returns an iterator to the first element 04009 * of the sub-sequence, or @p __last1 if the sub-sequence is not 04010 * found. 04011 * 04012 * Because the sub-sequence must lie completely within the range @p 04013 * [__first1,__last1) it must start at a position less than @p 04014 * __last1-(__last2-__first2) where @p __last2-__first2 is the 04015 * length of the sub-sequence. 04016 * 04017 * This means that the returned iterator @c i will be in the range 04018 * @p [__first1,__last1-(__last2-__first2)) 04019 */ 04020 template<typename _ForwardIterator1, typename _ForwardIterator2> 04021 inline _ForwardIterator1 04022 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04023 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 04024 { 04025 // concept requirements 04026 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 04027 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 04028 __glibcxx_function_requires(_EqualOpConcept< 04029 typename iterator_traits<_ForwardIterator1>::value_type, 04030 typename iterator_traits<_ForwardIterator2>::value_type>) 04031 __glibcxx_requires_valid_range(__first1, __last1); 04032 __glibcxx_requires_valid_range(__first2, __last2); 04033 04034 return std::__search(__first1, __last1, __first2, __last2, 04035 __gnu_cxx::__ops::__iter_equal_to_iter()); 04036 } 04037 04038 /** 04039 * @brief Search a sequence for a matching sub-sequence using a predicate. 04040 * @ingroup non_mutating_algorithms 04041 * @param __first1 A forward iterator. 04042 * @param __last1 A forward iterator. 04043 * @param __first2 A forward iterator. 04044 * @param __last2 A forward iterator. 04045 * @param __predicate A binary predicate. 04046 * @return The first iterator @c i in the range 04047 * @p [__first1,__last1-(__last2-__first2)) such that 04048 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range 04049 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists. 04050 * 04051 * Searches the range @p [__first1,__last1) for a sub-sequence that 04052 * compares equal value-by-value with the sequence given by @p 04053 * [__first2,__last2), using @p __predicate to determine equality, 04054 * and returns an iterator to the first element of the 04055 * sub-sequence, or @p __last1 if no such iterator exists. 04056 * 04057 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 04058 */ 04059 template<typename _ForwardIterator1, typename _ForwardIterator2, 04060 typename _BinaryPredicate> 04061 inline _ForwardIterator1 04062 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04063 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 04064 _BinaryPredicate __predicate) 04065 { 04066 // concept requirements 04067 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 04068 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 04069 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04070 typename iterator_traits<_ForwardIterator1>::value_type, 04071 typename iterator_traits<_ForwardIterator2>::value_type>) 04072 __glibcxx_requires_valid_range(__first1, __last1); 04073 __glibcxx_requires_valid_range(__first2, __last2); 04074 04075 return std::__search(__first1, __last1, __first2, __last2, 04076 __gnu_cxx::__ops::__iter_comp_iter(__predicate)); 04077 } 04078 04079 /** 04080 * @brief Search a sequence for a number of consecutive values. 04081 * @ingroup non_mutating_algorithms 04082 * @param __first A forward iterator. 04083 * @param __last A forward iterator. 04084 * @param __count The number of consecutive values. 04085 * @param __val The value to find. 04086 * @return The first iterator @c i in the range @p 04087 * [__first,__last-__count) such that @c *(i+N) == @p __val for 04088 * each @c N in the range @p [0,__count), or @p __last if no such 04089 * iterator exists. 04090 * 04091 * Searches the range @p [__first,__last) for @p count consecutive elements 04092 * equal to @p __val. 04093 */ 04094 template<typename _ForwardIterator, typename _Integer, typename _Tp> 04095 inline _ForwardIterator 04096 search_n(_ForwardIterator __first, _ForwardIterator __last, 04097 _Integer __count, const _Tp& __val) 04098 { 04099 // concept requirements 04100 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04101 __glibcxx_function_requires(_EqualOpConcept< 04102 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04103 __glibcxx_requires_valid_range(__first, __last); 04104 04105 return std::__search_n(__first, __last, __count, 04106 __gnu_cxx::__ops::__iter_equals_val(__val)); 04107 } 04108 04109 04110 /** 04111 * @brief Search a sequence for a number of consecutive values using a 04112 * predicate. 04113 * @ingroup non_mutating_algorithms 04114 * @param __first A forward iterator. 04115 * @param __last A forward iterator. 04116 * @param __count The number of consecutive values. 04117 * @param __val The value to find. 04118 * @param __binary_pred A binary predicate. 04119 * @return The first iterator @c i in the range @p 04120 * [__first,__last-__count) such that @p 04121 * __binary_pred(*(i+N),__val) is true for each @c N in the range 04122 * @p [0,__count), or @p __last if no such iterator exists. 04123 * 04124 * Searches the range @p [__first,__last) for @p __count 04125 * consecutive elements for which the predicate returns true. 04126 */ 04127 template<typename _ForwardIterator, typename _Integer, typename _Tp, 04128 typename _BinaryPredicate> 04129 inline _ForwardIterator 04130 search_n(_ForwardIterator __first, _ForwardIterator __last, 04131 _Integer __count, const _Tp& __val, 04132 _BinaryPredicate __binary_pred) 04133 { 04134 // concept requirements 04135 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04136 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04137 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04138 __glibcxx_requires_valid_range(__first, __last); 04139 04140 return std::__search_n(__first, __last, __count, 04141 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val)); 04142 } 04143 04144 04145 /** 04146 * @brief Perform an operation on a sequence. 04147 * @ingroup mutating_algorithms 04148 * @param __first An input iterator. 04149 * @param __last An input iterator. 04150 * @param __result An output iterator. 04151 * @param __unary_op A unary operator. 04152 * @return An output iterator equal to @p __result+(__last-__first). 04153 * 04154 * Applies the operator to each element in the input range and assigns 04155 * the results to successive elements of the output sequence. 04156 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the 04157 * range @p [0,__last-__first). 04158 * 04159 * @p unary_op must not alter its argument. 04160 */ 04161 template<typename _InputIterator, typename _OutputIterator, 04162 typename _UnaryOperation> 04163 _OutputIterator 04164 transform(_InputIterator __first, _InputIterator __last, 04165 _OutputIterator __result, _UnaryOperation __unary_op) 04166 { 04167 // concept requirements 04168 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04169 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04170 // "the type returned by a _UnaryOperation" 04171 __typeof__(__unary_op(*__first))>) 04172 __glibcxx_requires_valid_range(__first, __last); 04173 04174 for (; __first != __last; ++__first, ++__result) 04175 *__result = __unary_op(*__first); 04176 return __result; 04177 } 04178 04179 /** 04180 * @brief Perform an operation on corresponding elements of two sequences. 04181 * @ingroup mutating_algorithms 04182 * @param __first1 An input iterator. 04183 * @param __last1 An input iterator. 04184 * @param __first2 An input iterator. 04185 * @param __result An output iterator. 04186 * @param __binary_op A binary operator. 04187 * @return An output iterator equal to @p result+(last-first). 04188 * 04189 * Applies the operator to the corresponding elements in the two 04190 * input ranges and assigns the results to successive elements of the 04191 * output sequence. 04192 * Evaluates @p 04193 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each 04194 * @c N in the range @p [0,__last1-__first1). 04195 * 04196 * @p binary_op must not alter either of its arguments. 04197 */ 04198 template<typename _InputIterator1, typename _InputIterator2, 04199 typename _OutputIterator, typename _BinaryOperation> 04200 _OutputIterator 04201 transform(_InputIterator1 __first1, _InputIterator1 __last1, 04202 _InputIterator2 __first2, _OutputIterator __result, 04203 _BinaryOperation __binary_op) 04204 { 04205 // concept requirements 04206 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04207 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04208 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04209 // "the type returned by a _BinaryOperation" 04210 __typeof__(__binary_op(*__first1,*__first2))>) 04211 __glibcxx_requires_valid_range(__first1, __last1); 04212 04213 for (; __first1 != __last1; ++__first1, ++__first2, ++__result) 04214 *__result = __binary_op(*__first1, *__first2); 04215 return __result; 04216 } 04217 04218 /** 04219 * @brief Replace each occurrence of one value in a sequence with another 04220 * value. 04221 * @ingroup mutating_algorithms 04222 * @param __first A forward iterator. 04223 * @param __last A forward iterator. 04224 * @param __old_value The value to be replaced. 04225 * @param __new_value The replacement value. 04226 * @return replace() returns no value. 04227 * 04228 * For each iterator @c i in the range @p [__first,__last) if @c *i == 04229 * @p __old_value then the assignment @c *i = @p __new_value is performed. 04230 */ 04231 template<typename _ForwardIterator, typename _Tp> 04232 void 04233 replace(_ForwardIterator __first, _ForwardIterator __last, 04234 const _Tp& __old_value, const _Tp& __new_value) 04235 { 04236 // concept requirements 04237 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04238 _ForwardIterator>) 04239 __glibcxx_function_requires(_EqualOpConcept< 04240 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04241 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 04242 typename iterator_traits<_ForwardIterator>::value_type>) 04243 __glibcxx_requires_valid_range(__first, __last); 04244 04245 for (; __first != __last; ++__first) 04246 if (*__first == __old_value) 04247 *__first = __new_value; 04248 } 04249 04250 /** 04251 * @brief Replace each value in a sequence for which a predicate returns 04252 * true with another value. 04253 * @ingroup mutating_algorithms 04254 * @param __first A forward iterator. 04255 * @param __last A forward iterator. 04256 * @param __pred A predicate. 04257 * @param __new_value The replacement value. 04258 * @return replace_if() returns no value. 04259 * 04260 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i) 04261 * is true then the assignment @c *i = @p __new_value is performed. 04262 */ 04263 template<typename _ForwardIterator, typename _Predicate, typename _Tp> 04264 void 04265 replace_if(_ForwardIterator __first, _ForwardIterator __last, 04266 _Predicate __pred, const _Tp& __new_value) 04267 { 04268 // concept requirements 04269 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04270 _ForwardIterator>) 04271 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 04272 typename iterator_traits<_ForwardIterator>::value_type>) 04273 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 04274 typename iterator_traits<_ForwardIterator>::value_type>) 04275 __glibcxx_requires_valid_range(__first, __last); 04276 04277 for (; __first != __last; ++__first) 04278 if (__pred(*__first)) 04279 *__first = __new_value; 04280 } 04281 04282 /** 04283 * @brief Assign the result of a function object to each value in a 04284 * sequence. 04285 * @ingroup mutating_algorithms 04286 * @param __first A forward iterator. 04287 * @param __last A forward iterator. 04288 * @param __gen A function object taking no arguments and returning 04289 * std::iterator_traits<_ForwardIterator>::value_type 04290 * @return generate() returns no value. 04291 * 04292 * Performs the assignment @c *i = @p __gen() for each @c i in the range 04293 * @p [__first,__last). 04294 */ 04295 template<typename _ForwardIterator, typename _Generator> 04296 void 04297 generate(_ForwardIterator __first, _ForwardIterator __last, 04298 _Generator __gen) 04299 { 04300 // concept requirements 04301 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04302 __glibcxx_function_requires(_GeneratorConcept<_Generator, 04303 typename iterator_traits<_ForwardIterator>::value_type>) 04304 __glibcxx_requires_valid_range(__first, __last); 04305 04306 for (; __first != __last; ++__first) 04307 *__first = __gen(); 04308 } 04309 04310 /** 04311 * @brief Assign the result of a function object to each value in a 04312 * sequence. 04313 * @ingroup mutating_algorithms 04314 * @param __first A forward iterator. 04315 * @param __n The length of the sequence. 04316 * @param __gen A function object taking no arguments and returning 04317 * std::iterator_traits<_ForwardIterator>::value_type 04318 * @return The end of the sequence, @p __first+__n 04319 * 04320 * Performs the assignment @c *i = @p __gen() for each @c i in the range 04321 * @p [__first,__first+__n). 04322 * 04323 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04324 * DR 865. More algorithms that throw away information 04325 */ 04326 template<typename _OutputIterator, typename _Size, typename _Generator> 04327 _OutputIterator 04328 generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 04329 { 04330 // concept requirements 04331 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04332 // "the type returned by a _Generator" 04333 __typeof__(__gen())>) 04334 04335 for (__decltype(__n + 0) __niter = __n; 04336 __niter > 0; --__niter, ++__first) 04337 *__first = __gen(); 04338 return __first; 04339 } 04340 04341 /** 04342 * @brief Copy a sequence, removing consecutive duplicate values. 04343 * @ingroup mutating_algorithms 04344 * @param __first An input iterator. 04345 * @param __last An input iterator. 04346 * @param __result An output iterator. 04347 * @return An iterator designating the end of the resulting sequence. 04348 * 04349 * Copies each element in the range @p [__first,__last) to the range 04350 * beginning at @p __result, except that only the first element is copied 04351 * from groups of consecutive elements that compare equal. 04352 * unique_copy() is stable, so the relative order of elements that are 04353 * copied is unchanged. 04354 * 04355 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04356 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 04357 * 04358 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04359 * DR 538. 241 again: Does unique_copy() require CopyConstructible and 04360 * Assignable? 04361 */ 04362 template<typename _InputIterator, typename _OutputIterator> 04363 inline _OutputIterator 04364 unique_copy(_InputIterator __first, _InputIterator __last, 04365 _OutputIterator __result) 04366 { 04367 // concept requirements 04368 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04369 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04370 typename iterator_traits<_InputIterator>::value_type>) 04371 __glibcxx_function_requires(_EqualityComparableConcept< 04372 typename iterator_traits<_InputIterator>::value_type>) 04373 __glibcxx_requires_valid_range(__first, __last); 04374 04375 if (__first == __last) 04376 return __result; 04377 return std::__unique_copy(__first, __last, __result, 04378 __gnu_cxx::__ops::__iter_equal_to_iter(), 04379 std::__iterator_category(__first), 04380 std::__iterator_category(__result)); 04381 } 04382 04383 /** 04384 * @brief Copy a sequence, removing consecutive values using a predicate. 04385 * @ingroup mutating_algorithms 04386 * @param __first An input iterator. 04387 * @param __last An input iterator. 04388 * @param __result An output iterator. 04389 * @param __binary_pred A binary predicate. 04390 * @return An iterator designating the end of the resulting sequence. 04391 * 04392 * Copies each element in the range @p [__first,__last) to the range 04393 * beginning at @p __result, except that only the first element is copied 04394 * from groups of consecutive elements for which @p __binary_pred returns 04395 * true. 04396 * unique_copy() is stable, so the relative order of elements that are 04397 * copied is unchanged. 04398 * 04399 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04400 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 04401 */ 04402 template<typename _InputIterator, typename _OutputIterator, 04403 typename _BinaryPredicate> 04404 inline _OutputIterator 04405 unique_copy(_InputIterator __first, _InputIterator __last, 04406 _OutputIterator __result, 04407 _BinaryPredicate __binary_pred) 04408 { 04409 // concept requirements -- predicates checked later 04410 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04411 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04412 typename iterator_traits<_InputIterator>::value_type>) 04413 __glibcxx_requires_valid_range(__first, __last); 04414 04415 if (__first == __last) 04416 return __result; 04417 return std::__unique_copy(__first, __last, __result, 04418 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred), 04419 std::__iterator_category(__first), 04420 std::__iterator_category(__result)); 04421 } 04422 04423 /** 04424 * @brief Randomly shuffle the elements of a sequence. 04425 * @ingroup mutating_algorithms 04426 * @param __first A forward iterator. 04427 * @param __last A forward iterator. 04428 * @return Nothing. 04429 * 04430 * Reorder the elements in the range @p [__first,__last) using a random 04431 * distribution, so that every possible ordering of the sequence is 04432 * equally likely. 04433 */ 04434 template<typename _RandomAccessIterator> 04435 inline void 04436 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 04437 { 04438 // concept requirements 04439 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04440 _RandomAccessIterator>) 04441 __glibcxx_requires_valid_range(__first, __last); 04442 04443 if (__first != __last) 04444 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 04445 { 04446 // XXX rand() % N is not uniformly distributed 04447 _RandomAccessIterator __j = __first 04448 + std::rand() % ((__i - __first) + 1); 04449 if (__i != __j) 04450 std::iter_swap(__i, __j); 04451 } 04452 } 04453 04454 /** 04455 * @brief Shuffle the elements of a sequence using a random number 04456 * generator. 04457 * @ingroup mutating_algorithms 04458 * @param __first A forward iterator. 04459 * @param __last A forward iterator. 04460 * @param __rand The RNG functor or function. 04461 * @return Nothing. 04462 * 04463 * Reorders the elements in the range @p [__first,__last) using @p __rand to 04464 * provide a random distribution. Calling @p __rand(N) for a positive 04465 * integer @p N should return a randomly chosen integer from the 04466 * range [0,N). 04467 */ 04468 template<typename _RandomAccessIterator, typename _RandomNumberGenerator> 04469 void 04470 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 04471 #if __cplusplus >= 201103L 04472 _RandomNumberGenerator&& __rand) 04473 #else 04474 _RandomNumberGenerator& __rand) 04475 #endif 04476 { 04477 // concept requirements 04478 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04479 _RandomAccessIterator>) 04480 __glibcxx_requires_valid_range(__first, __last); 04481 04482 if (__first == __last) 04483 return; 04484 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 04485 { 04486 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1); 04487 if (__i != __j) 04488 std::iter_swap(__i, __j); 04489 } 04490 } 04491 04492 04493 /** 04494 * @brief Move elements for which a predicate is true to the beginning 04495 * of a sequence. 04496 * @ingroup mutating_algorithms 04497 * @param __first A forward iterator. 04498 * @param __last A forward iterator. 04499 * @param __pred A predicate functor. 04500 * @return An iterator @p middle such that @p __pred(i) is true for each 04501 * iterator @p i in the range @p [__first,middle) and false for each @p i 04502 * in the range @p [middle,__last). 04503 * 04504 * @p __pred must not modify its operand. @p partition() does not preserve 04505 * the relative ordering of elements in each group, use 04506 * @p stable_partition() if this is needed. 04507 */ 04508 template<typename _ForwardIterator, typename _Predicate> 04509 inline _ForwardIterator 04510 partition(_ForwardIterator __first, _ForwardIterator __last, 04511 _Predicate __pred) 04512 { 04513 // concept requirements 04514 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04515 _ForwardIterator>) 04516 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 04517 typename iterator_traits<_ForwardIterator>::value_type>) 04518 __glibcxx_requires_valid_range(__first, __last); 04519 04520 return std::__partition(__first, __last, __pred, 04521 std::__iterator_category(__first)); 04522 } 04523 04524 04525 /** 04526 * @brief Sort the smallest elements of a sequence. 04527 * @ingroup sorting_algorithms 04528 * @param __first An iterator. 04529 * @param __middle Another iterator. 04530 * @param __last Another iterator. 04531 * @return Nothing. 04532 * 04533 * Sorts the smallest @p (__middle-__first) elements in the range 04534 * @p [first,last) and moves them to the range @p [__first,__middle). The 04535 * order of the remaining elements in the range @p [__middle,__last) is 04536 * undefined. 04537 * After the sort if @e i and @e j are iterators in the range 04538 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 04539 * the range @p [__middle,__last) then *j<*i and *k<*i are both false. 04540 */ 04541 template<typename _RandomAccessIterator> 04542 inline void 04543 partial_sort(_RandomAccessIterator __first, 04544 _RandomAccessIterator __middle, 04545 _RandomAccessIterator __last) 04546 { 04547 // concept requirements 04548 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04549 _RandomAccessIterator>) 04550 __glibcxx_function_requires(_LessThanComparableConcept< 04551 typename iterator_traits<_RandomAccessIterator>::value_type>) 04552 __glibcxx_requires_valid_range(__first, __middle); 04553 __glibcxx_requires_valid_range(__middle, __last); 04554 04555 std::__partial_sort(__first, __middle, __last, 04556 __gnu_cxx::__ops::__iter_less_iter()); 04557 } 04558 04559 /** 04560 * @brief Sort the smallest elements of a sequence using a predicate 04561 * for comparison. 04562 * @ingroup sorting_algorithms 04563 * @param __first An iterator. 04564 * @param __middle Another iterator. 04565 * @param __last Another iterator. 04566 * @param __comp A comparison functor. 04567 * @return Nothing. 04568 * 04569 * Sorts the smallest @p (__middle-__first) elements in the range 04570 * @p [__first,__last) and moves them to the range @p [__first,__middle). The 04571 * order of the remaining elements in the range @p [__middle,__last) is 04572 * undefined. 04573 * After the sort if @e i and @e j are iterators in the range 04574 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 04575 * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i) 04576 * are both false. 04577 */ 04578 template<typename _RandomAccessIterator, typename _Compare> 04579 inline void 04580 partial_sort(_RandomAccessIterator __first, 04581 _RandomAccessIterator __middle, 04582 _RandomAccessIterator __last, 04583 _Compare __comp) 04584 { 04585 // concept requirements 04586 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04587 _RandomAccessIterator>) 04588 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04589 typename iterator_traits<_RandomAccessIterator>::value_type, 04590 typename iterator_traits<_RandomAccessIterator>::value_type>) 04591 __glibcxx_requires_valid_range(__first, __middle); 04592 __glibcxx_requires_valid_range(__middle, __last); 04593 04594 std::__partial_sort(__first, __middle, __last, 04595 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04596 } 04597 04598 /** 04599 * @brief Sort a sequence just enough to find a particular position. 04600 * @ingroup sorting_algorithms 04601 * @param __first An iterator. 04602 * @param __nth Another iterator. 04603 * @param __last Another iterator. 04604 * @return Nothing. 04605 * 04606 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 04607 * is the same element that would have been in that position had the 04608 * whole sequence been sorted. The elements either side of @p *__nth are 04609 * not completely sorted, but for any iterator @e i in the range 04610 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 04611 * holds that *j < *i is false. 04612 */ 04613 template<typename _RandomAccessIterator> 04614 inline void 04615 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 04616 _RandomAccessIterator __last) 04617 { 04618 // concept requirements 04619 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04620 _RandomAccessIterator>) 04621 __glibcxx_function_requires(_LessThanComparableConcept< 04622 typename iterator_traits<_RandomAccessIterator>::value_type>) 04623 __glibcxx_requires_valid_range(__first, __nth); 04624 __glibcxx_requires_valid_range(__nth, __last); 04625 04626 if (__first == __last || __nth == __last) 04627 return; 04628 04629 std::__introselect(__first, __nth, __last, 04630 std::__lg(__last - __first) * 2, 04631 __gnu_cxx::__ops::__iter_less_iter()); 04632 } 04633 04634 /** 04635 * @brief Sort a sequence just enough to find a particular position 04636 * using a predicate for comparison. 04637 * @ingroup sorting_algorithms 04638 * @param __first An iterator. 04639 * @param __nth Another iterator. 04640 * @param __last Another iterator. 04641 * @param __comp A comparison functor. 04642 * @return Nothing. 04643 * 04644 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 04645 * is the same element that would have been in that position had the 04646 * whole sequence been sorted. The elements either side of @p *__nth are 04647 * not completely sorted, but for any iterator @e i in the range 04648 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 04649 * holds that @p __comp(*j,*i) is false. 04650 */ 04651 template<typename _RandomAccessIterator, typename _Compare> 04652 inline void 04653 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 04654 _RandomAccessIterator __last, _Compare __comp) 04655 { 04656 // concept requirements 04657 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04658 _RandomAccessIterator>) 04659 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04660 typename iterator_traits<_RandomAccessIterator>::value_type, 04661 typename iterator_traits<_RandomAccessIterator>::value_type>) 04662 __glibcxx_requires_valid_range(__first, __nth); 04663 __glibcxx_requires_valid_range(__nth, __last); 04664 04665 if (__first == __last || __nth == __last) 04666 return; 04667 04668 std::__introselect(__first, __nth, __last, 04669 std::__lg(__last - __first) * 2, 04670 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04671 } 04672 04673 /** 04674 * @brief Sort the elements of a sequence. 04675 * @ingroup sorting_algorithms 04676 * @param __first An iterator. 04677 * @param __last Another iterator. 04678 * @return Nothing. 04679 * 04680 * Sorts the elements in the range @p [__first,__last) in ascending order, 04681 * such that for each iterator @e i in the range @p [__first,__last-1), 04682 * *(i+1)<*i is false. 04683 * 04684 * The relative ordering of equivalent elements is not preserved, use 04685 * @p stable_sort() if this is needed. 04686 */ 04687 template<typename _RandomAccessIterator> 04688 inline void 04689 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 04690 { 04691 // concept requirements 04692 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04693 _RandomAccessIterator>) 04694 __glibcxx_function_requires(_LessThanComparableConcept< 04695 typename iterator_traits<_RandomAccessIterator>::value_type>) 04696 __glibcxx_requires_valid_range(__first, __last); 04697 04698 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 04699 } 04700 04701 /** 04702 * @brief Sort the elements of a sequence using a predicate for comparison. 04703 * @ingroup sorting_algorithms 04704 * @param __first An iterator. 04705 * @param __last Another iterator. 04706 * @param __comp A comparison functor. 04707 * @return Nothing. 04708 * 04709 * Sorts the elements in the range @p [__first,__last) in ascending order, 04710 * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the 04711 * range @p [__first,__last-1). 04712 * 04713 * The relative ordering of equivalent elements is not preserved, use 04714 * @p stable_sort() if this is needed. 04715 */ 04716 template<typename _RandomAccessIterator, typename _Compare> 04717 inline void 04718 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 04719 _Compare __comp) 04720 { 04721 // concept requirements 04722 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04723 _RandomAccessIterator>) 04724 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04725 typename iterator_traits<_RandomAccessIterator>::value_type, 04726 typename iterator_traits<_RandomAccessIterator>::value_type>) 04727 __glibcxx_requires_valid_range(__first, __last); 04728 04729 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04730 } 04731 04732 template<typename _InputIterator1, typename _InputIterator2, 04733 typename _OutputIterator, typename _Compare> 04734 _OutputIterator 04735 __merge(_InputIterator1 __first1, _InputIterator1 __last1, 04736 _InputIterator2 __first2, _InputIterator2 __last2, 04737 _OutputIterator __result, _Compare __comp) 04738 { 04739 while (__first1 != __last1 && __first2 != __last2) 04740 { 04741 if (__comp(__first2, __first1)) 04742 { 04743 *__result = *__first2; 04744 ++__first2; 04745 } 04746 else 04747 { 04748 *__result = *__first1; 04749 ++__first1; 04750 } 04751 ++__result; 04752 } 04753 return std::copy(__first2, __last2, 04754 std::copy(__first1, __last1, __result)); 04755 } 04756 04757 /** 04758 * @brief Merges two sorted ranges. 04759 * @ingroup sorting_algorithms 04760 * @param __first1 An iterator. 04761 * @param __first2 Another iterator. 04762 * @param __last1 Another iterator. 04763 * @param __last2 Another iterator. 04764 * @param __result An iterator pointing to the end of the merged range. 04765 * @return An iterator pointing to the first element <em>not less 04766 * than</em> @e val. 04767 * 04768 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 04769 * the sorted range @p [__result, __result + (__last1-__first1) + 04770 * (__last2-__first2)). Both input ranges must be sorted, and the 04771 * output range must not overlap with either of the input ranges. 04772 * The sort is @e stable, that is, for equivalent elements in the 04773 * two ranges, elements from the first range will always come 04774 * before elements from the second. 04775 */ 04776 template<typename _InputIterator1, typename _InputIterator2, 04777 typename _OutputIterator> 04778 inline _OutputIterator 04779 merge(_InputIterator1 __first1, _InputIterator1 __last1, 04780 _InputIterator2 __first2, _InputIterator2 __last2, 04781 _OutputIterator __result) 04782 { 04783 // concept requirements 04784 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04785 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04786 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04787 typename iterator_traits<_InputIterator1>::value_type>) 04788 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04789 typename iterator_traits<_InputIterator2>::value_type>) 04790 __glibcxx_function_requires(_LessThanOpConcept< 04791 typename iterator_traits<_InputIterator2>::value_type, 04792 typename iterator_traits<_InputIterator1>::value_type>) 04793 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 04794 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 04795 04796 return _GLIBCXX_STD_A::__merge(__first1, __last1, 04797 __first2, __last2, __result, 04798 __gnu_cxx::__ops::__iter_less_iter()); 04799 } 04800 04801 /** 04802 * @brief Merges two sorted ranges. 04803 * @ingroup sorting_algorithms 04804 * @param __first1 An iterator. 04805 * @param __first2 Another iterator. 04806 * @param __last1 Another iterator. 04807 * @param __last2 Another iterator. 04808 * @param __result An iterator pointing to the end of the merged range. 04809 * @param __comp A functor to use for comparisons. 04810 * @return An iterator pointing to the first element "not less 04811 * than" @e val. 04812 * 04813 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 04814 * the sorted range @p [__result, __result + (__last1-__first1) + 04815 * (__last2-__first2)). Both input ranges must be sorted, and the 04816 * output range must not overlap with either of the input ranges. 04817 * The sort is @e stable, that is, for equivalent elements in the 04818 * two ranges, elements from the first range will always come 04819 * before elements from the second. 04820 * 04821 * The comparison function should have the same effects on ordering as 04822 * the function used for the initial sort. 04823 */ 04824 template<typename _InputIterator1, typename _InputIterator2, 04825 typename _OutputIterator, typename _Compare> 04826 inline _OutputIterator 04827 merge(_InputIterator1 __first1, _InputIterator1 __last1, 04828 _InputIterator2 __first2, _InputIterator2 __last2, 04829 _OutputIterator __result, _Compare __comp) 04830 { 04831 // concept requirements 04832 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04833 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04834 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04835 typename iterator_traits<_InputIterator1>::value_type>) 04836 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04837 typename iterator_traits<_InputIterator2>::value_type>) 04838 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04839 typename iterator_traits<_InputIterator2>::value_type, 04840 typename iterator_traits<_InputIterator1>::value_type>) 04841 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 04842 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 04843 04844 return _GLIBCXX_STD_A::__merge(__first1, __last1, 04845 __first2, __last2, __result, 04846 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04847 } 04848 04849 template<typename _RandomAccessIterator, typename _Compare> 04850 inline void 04851 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 04852 _Compare __comp) 04853 { 04854 typedef typename iterator_traits<_RandomAccessIterator>::value_type 04855 _ValueType; 04856 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 04857 _DistanceType; 04858 04859 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf; 04860 _TmpBuf __buf(__first, __last); 04861 04862 if (__buf.begin() == 0) 04863 std::__inplace_stable_sort(__first, __last, __comp); 04864 else 04865 std::__stable_sort_adaptive(__first, __last, __buf.begin(), 04866 _DistanceType(__buf.size()), __comp); 04867 } 04868 04869 /** 04870 * @brief Sort the elements of a sequence, preserving the relative order 04871 * of equivalent elements. 04872 * @ingroup sorting_algorithms 04873 * @param __first An iterator. 04874 * @param __last Another iterator. 04875 * @return Nothing. 04876 * 04877 * Sorts the elements in the range @p [__first,__last) in ascending order, 04878 * such that for each iterator @p i in the range @p [__first,__last-1), 04879 * @p *(i+1)<*i is false. 04880 * 04881 * The relative ordering of equivalent elements is preserved, so any two 04882 * elements @p x and @p y in the range @p [__first,__last) such that 04883 * @p x<y is false and @p y<x is false will have the same relative 04884 * ordering after calling @p stable_sort(). 04885 */ 04886 template<typename _RandomAccessIterator> 04887 inline void 04888 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 04889 { 04890 // concept requirements 04891 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04892 _RandomAccessIterator>) 04893 __glibcxx_function_requires(_LessThanComparableConcept< 04894 typename iterator_traits<_RandomAccessIterator>::value_type>) 04895 __glibcxx_requires_valid_range(__first, __last); 04896 04897 _GLIBCXX_STD_A::__stable_sort(__first, __last, 04898 __gnu_cxx::__ops::__iter_less_iter()); 04899 } 04900 04901 /** 04902 * @brief Sort the elements of a sequence using a predicate for comparison, 04903 * preserving the relative order of equivalent elements. 04904 * @ingroup sorting_algorithms 04905 * @param __first An iterator. 04906 * @param __last Another iterator. 04907 * @param __comp A comparison functor. 04908 * @return Nothing. 04909 * 04910 * Sorts the elements in the range @p [__first,__last) in ascending order, 04911 * such that for each iterator @p i in the range @p [__first,__last-1), 04912 * @p __comp(*(i+1),*i) is false. 04913 * 04914 * The relative ordering of equivalent elements is preserved, so any two 04915 * elements @p x and @p y in the range @p [__first,__last) such that 04916 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same 04917 * relative ordering after calling @p stable_sort(). 04918 */ 04919 template<typename _RandomAccessIterator, typename _Compare> 04920 inline void 04921 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 04922 _Compare __comp) 04923 { 04924 // concept requirements 04925 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04926 _RandomAccessIterator>) 04927 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04928 typename iterator_traits<_RandomAccessIterator>::value_type, 04929 typename iterator_traits<_RandomAccessIterator>::value_type>) 04930 __glibcxx_requires_valid_range(__first, __last); 04931 04932 _GLIBCXX_STD_A::__stable_sort(__first, __last, 04933 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04934 } 04935 04936 template<typename _InputIterator1, typename _InputIterator2, 04937 typename _OutputIterator, 04938 typename _Compare> 04939 _OutputIterator 04940 __set_union(_InputIterator1 __first1, _InputIterator1 __last1, 04941 _InputIterator2 __first2, _InputIterator2 __last2, 04942 _OutputIterator __result, _Compare __comp) 04943 { 04944 while (__first1 != __last1 && __first2 != __last2) 04945 { 04946 if (__comp(__first1, __first2)) 04947 { 04948 *__result = *__first1; 04949 ++__first1; 04950 } 04951 else if (__comp(__first2, __first1)) 04952 { 04953 *__result = *__first2; 04954 ++__first2; 04955 } 04956 else 04957 { 04958 *__result = *__first1; 04959 ++__first1; 04960 ++__first2; 04961 } 04962 ++__result; 04963 } 04964 return std::copy(__first2, __last2, 04965 std::copy(__first1, __last1, __result)); 04966 } 04967 04968 /** 04969 * @brief Return the union of two sorted ranges. 04970 * @ingroup set_algorithms 04971 * @param __first1 Start of first range. 04972 * @param __last1 End of first range. 04973 * @param __first2 Start of second range. 04974 * @param __last2 End of second range. 04975 * @return End of the output range. 04976 * @ingroup set_algorithms 04977 * 04978 * This operation iterates over both ranges, copying elements present in 04979 * each range in order to the output range. Iterators increment for each 04980 * range. When the current element of one range is less than the other, 04981 * that element is copied and the iterator advanced. If an element is 04982 * contained in both ranges, the element from the first range is copied and 04983 * both ranges advance. The output range may not overlap either input 04984 * range. 04985 */ 04986 template<typename _InputIterator1, typename _InputIterator2, 04987 typename _OutputIterator> 04988 inline _OutputIterator 04989 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 04990 _InputIterator2 __first2, _InputIterator2 __last2, 04991 _OutputIterator __result) 04992 { 04993 // concept requirements 04994 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04995 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04996 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04997 typename iterator_traits<_InputIterator1>::value_type>) 04998 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04999 typename iterator_traits<_InputIterator2>::value_type>) 05000 __glibcxx_function_requires(_LessThanOpConcept< 05001 typename iterator_traits<_InputIterator1>::value_type, 05002 typename iterator_traits<_InputIterator2>::value_type>) 05003 __glibcxx_function_requires(_LessThanOpConcept< 05004 typename iterator_traits<_InputIterator2>::value_type, 05005 typename iterator_traits<_InputIterator1>::value_type>) 05006 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05007 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05008 05009 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 05010 __first2, __last2, __result, 05011 __gnu_cxx::__ops::__iter_less_iter()); 05012 } 05013 05014 /** 05015 * @brief Return the union of two sorted ranges using a comparison functor. 05016 * @ingroup set_algorithms 05017 * @param __first1 Start of first range. 05018 * @param __last1 End of first range. 05019 * @param __first2 Start of second range. 05020 * @param __last2 End of second range. 05021 * @param __comp The comparison functor. 05022 * @return End of the output range. 05023 * @ingroup set_algorithms 05024 * 05025 * This operation iterates over both ranges, copying elements present in 05026 * each range in order to the output range. Iterators increment for each 05027 * range. When the current element of one range is less than the other 05028 * according to @p __comp, that element is copied and the iterator advanced. 05029 * If an equivalent element according to @p __comp is contained in both 05030 * ranges, the element from the first range is copied and both ranges 05031 * advance. The output range may not overlap either input range. 05032 */ 05033 template<typename _InputIterator1, typename _InputIterator2, 05034 typename _OutputIterator, typename _Compare> 05035 inline _OutputIterator 05036 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 05037 _InputIterator2 __first2, _InputIterator2 __last2, 05038 _OutputIterator __result, _Compare __comp) 05039 { 05040 // concept requirements 05041 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05042 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05043 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05044 typename iterator_traits<_InputIterator1>::value_type>) 05045 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05046 typename iterator_traits<_InputIterator2>::value_type>) 05047 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05048 typename iterator_traits<_InputIterator1>::value_type, 05049 typename iterator_traits<_InputIterator2>::value_type>) 05050 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05051 typename iterator_traits<_InputIterator2>::value_type, 05052 typename iterator_traits<_InputIterator1>::value_type>) 05053 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05054 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05055 05056 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 05057 __first2, __last2, __result, 05058 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05059 } 05060 05061 template<typename _InputIterator1, typename _InputIterator2, 05062 typename _OutputIterator, 05063 typename _Compare> 05064 _OutputIterator 05065 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05066 _InputIterator2 __first2, _InputIterator2 __last2, 05067 _OutputIterator __result, _Compare __comp) 05068 { 05069 while (__first1 != __last1 && __first2 != __last2) 05070 if (__comp(__first1, __first2)) 05071 ++__first1; 05072 else if (__comp(__first2, __first1)) 05073 ++__first2; 05074 else 05075 { 05076 *__result = *__first1; 05077 ++__first1; 05078 ++__first2; 05079 ++__result; 05080 } 05081 return __result; 05082 } 05083 05084 /** 05085 * @brief Return the intersection of two sorted ranges. 05086 * @ingroup set_algorithms 05087 * @param __first1 Start of first range. 05088 * @param __last1 End of first range. 05089 * @param __first2 Start of second range. 05090 * @param __last2 End of second range. 05091 * @return End of the output range. 05092 * @ingroup set_algorithms 05093 * 05094 * This operation iterates over both ranges, copying elements present in 05095 * both ranges in order to the output range. Iterators increment for each 05096 * range. When the current element of one range is less than the other, 05097 * that iterator advances. If an element is contained in both ranges, the 05098 * element from the first range is copied and both ranges advance. The 05099 * output range may not overlap either input range. 05100 */ 05101 template<typename _InputIterator1, typename _InputIterator2, 05102 typename _OutputIterator> 05103 inline _OutputIterator 05104 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05105 _InputIterator2 __first2, _InputIterator2 __last2, 05106 _OutputIterator __result) 05107 { 05108 // concept requirements 05109 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05110 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05111 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05112 typename iterator_traits<_InputIterator1>::value_type>) 05113 __glibcxx_function_requires(_LessThanOpConcept< 05114 typename iterator_traits<_InputIterator1>::value_type, 05115 typename iterator_traits<_InputIterator2>::value_type>) 05116 __glibcxx_function_requires(_LessThanOpConcept< 05117 typename iterator_traits<_InputIterator2>::value_type, 05118 typename iterator_traits<_InputIterator1>::value_type>) 05119 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05120 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05121 05122 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 05123 __first2, __last2, __result, 05124 __gnu_cxx::__ops::__iter_less_iter()); 05125 } 05126 05127 /** 05128 * @brief Return the intersection of two sorted ranges using comparison 05129 * functor. 05130 * @ingroup set_algorithms 05131 * @param __first1 Start of first range. 05132 * @param __last1 End of first range. 05133 * @param __first2 Start of second range. 05134 * @param __last2 End of second range. 05135 * @param __comp The comparison functor. 05136 * @return End of the output range. 05137 * @ingroup set_algorithms 05138 * 05139 * This operation iterates over both ranges, copying elements present in 05140 * both ranges in order to the output range. Iterators increment for each 05141 * range. When the current element of one range is less than the other 05142 * according to @p __comp, that iterator advances. If an element is 05143 * contained in both ranges according to @p __comp, the element from the 05144 * first range is copied and both ranges advance. The output range may not 05145 * overlap either input range. 05146 */ 05147 template<typename _InputIterator1, typename _InputIterator2, 05148 typename _OutputIterator, typename _Compare> 05149 inline _OutputIterator 05150 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05151 _InputIterator2 __first2, _InputIterator2 __last2, 05152 _OutputIterator __result, _Compare __comp) 05153 { 05154 // concept requirements 05155 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05156 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05157 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05158 typename iterator_traits<_InputIterator1>::value_type>) 05159 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05160 typename iterator_traits<_InputIterator1>::value_type, 05161 typename iterator_traits<_InputIterator2>::value_type>) 05162 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05163 typename iterator_traits<_InputIterator2>::value_type, 05164 typename iterator_traits<_InputIterator1>::value_type>) 05165 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05166 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05167 05168 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 05169 __first2, __last2, __result, 05170 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05171 } 05172 05173 template<typename _InputIterator1, typename _InputIterator2, 05174 typename _OutputIterator, 05175 typename _Compare> 05176 _OutputIterator 05177 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05178 _InputIterator2 __first2, _InputIterator2 __last2, 05179 _OutputIterator __result, _Compare __comp) 05180 { 05181 while (__first1 != __last1 && __first2 != __last2) 05182 if (__comp(__first1, __first2)) 05183 { 05184 *__result = *__first1; 05185 ++__first1; 05186 ++__result; 05187 } 05188 else if (__comp(__first2, __first1)) 05189 ++__first2; 05190 else 05191 { 05192 ++__first1; 05193 ++__first2; 05194 } 05195 return std::copy(__first1, __last1, __result); 05196 } 05197 05198 /** 05199 * @brief Return the difference of two sorted ranges. 05200 * @ingroup set_algorithms 05201 * @param __first1 Start of first range. 05202 * @param __last1 End of first range. 05203 * @param __first2 Start of second range. 05204 * @param __last2 End of second range. 05205 * @return End of the output range. 05206 * @ingroup set_algorithms 05207 * 05208 * This operation iterates over both ranges, copying elements present in 05209 * the first range but not the second in order to the output range. 05210 * Iterators increment for each range. When the current element of the 05211 * first range is less than the second, that element is copied and the 05212 * iterator advances. If the current element of the second range is less, 05213 * the iterator advances, but no element is copied. If an element is 05214 * contained in both ranges, no elements are copied and both ranges 05215 * advance. The output range may not overlap either input range. 05216 */ 05217 template<typename _InputIterator1, typename _InputIterator2, 05218 typename _OutputIterator> 05219 inline _OutputIterator 05220 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05221 _InputIterator2 __first2, _InputIterator2 __last2, 05222 _OutputIterator __result) 05223 { 05224 // concept requirements 05225 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05226 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05227 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05228 typename iterator_traits<_InputIterator1>::value_type>) 05229 __glibcxx_function_requires(_LessThanOpConcept< 05230 typename iterator_traits<_InputIterator1>::value_type, 05231 typename iterator_traits<_InputIterator2>::value_type>) 05232 __glibcxx_function_requires(_LessThanOpConcept< 05233 typename iterator_traits<_InputIterator2>::value_type, 05234 typename iterator_traits<_InputIterator1>::value_type>) 05235 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05236 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05237 05238 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 05239 __first2, __last2, __result, 05240 __gnu_cxx::__ops::__iter_less_iter()); 05241 } 05242 05243 /** 05244 * @brief Return the difference of two sorted ranges using comparison 05245 * functor. 05246 * @ingroup set_algorithms 05247 * @param __first1 Start of first range. 05248 * @param __last1 End of first range. 05249 * @param __first2 Start of second range. 05250 * @param __last2 End of second range. 05251 * @param __comp The comparison functor. 05252 * @return End of the output range. 05253 * @ingroup set_algorithms 05254 * 05255 * This operation iterates over both ranges, copying elements present in 05256 * the first range but not the second in order to the output range. 05257 * Iterators increment for each range. When the current element of the 05258 * first range is less than the second according to @p __comp, that element 05259 * is copied and the iterator advances. If the current element of the 05260 * second range is less, no element is copied and the iterator advances. 05261 * If an element is contained in both ranges according to @p __comp, no 05262 * elements are copied and both ranges advance. The output range may not 05263 * overlap either input range. 05264 */ 05265 template<typename _InputIterator1, typename _InputIterator2, 05266 typename _OutputIterator, typename _Compare> 05267 inline _OutputIterator 05268 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05269 _InputIterator2 __first2, _InputIterator2 __last2, 05270 _OutputIterator __result, _Compare __comp) 05271 { 05272 // concept requirements 05273 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05274 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05275 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05276 typename iterator_traits<_InputIterator1>::value_type>) 05277 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05278 typename iterator_traits<_InputIterator1>::value_type, 05279 typename iterator_traits<_InputIterator2>::value_type>) 05280 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05281 typename iterator_traits<_InputIterator2>::value_type, 05282 typename iterator_traits<_InputIterator1>::value_type>) 05283 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05284 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05285 05286 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 05287 __first2, __last2, __result, 05288 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05289 } 05290 05291 template<typename _InputIterator1, typename _InputIterator2, 05292 typename _OutputIterator, 05293 typename _Compare> 05294 _OutputIterator 05295 __set_symmetric_difference(_InputIterator1 __first1, 05296 _InputIterator1 __last1, 05297 _InputIterator2 __first2, 05298 _InputIterator2 __last2, 05299 _OutputIterator __result, 05300 _Compare __comp) 05301 { 05302 while (__first1 != __last1 && __first2 != __last2) 05303 if (__comp(__first1, __first2)) 05304 { 05305 *__result = *__first1; 05306 ++__first1; 05307 ++__result; 05308 } 05309 else if (__comp(__first2, __first1)) 05310 { 05311 *__result = *__first2; 05312 ++__first2; 05313 ++__result; 05314 } 05315 else 05316 { 05317 ++__first1; 05318 ++__first2; 05319 } 05320 return std::copy(__first2, __last2, 05321 std::copy(__first1, __last1, __result)); 05322 } 05323 05324 /** 05325 * @brief Return the symmetric difference of two sorted ranges. 05326 * @ingroup set_algorithms 05327 * @param __first1 Start of first range. 05328 * @param __last1 End of first range. 05329 * @param __first2 Start of second range. 05330 * @param __last2 End of second range. 05331 * @return End of the output range. 05332 * @ingroup set_algorithms 05333 * 05334 * This operation iterates over both ranges, copying elements present in 05335 * one range but not the other in order to the output range. Iterators 05336 * increment for each range. When the current element of one range is less 05337 * than the other, that element is copied and the iterator advances. If an 05338 * element is contained in both ranges, no elements are copied and both 05339 * ranges advance. The output range may not overlap either input range. 05340 */ 05341 template<typename _InputIterator1, typename _InputIterator2, 05342 typename _OutputIterator> 05343 inline _OutputIterator 05344 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05345 _InputIterator2 __first2, _InputIterator2 __last2, 05346 _OutputIterator __result) 05347 { 05348 // concept requirements 05349 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05350 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05351 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05352 typename iterator_traits<_InputIterator1>::value_type>) 05353 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05354 typename iterator_traits<_InputIterator2>::value_type>) 05355 __glibcxx_function_requires(_LessThanOpConcept< 05356 typename iterator_traits<_InputIterator1>::value_type, 05357 typename iterator_traits<_InputIterator2>::value_type>) 05358 __glibcxx_function_requires(_LessThanOpConcept< 05359 typename iterator_traits<_InputIterator2>::value_type, 05360 typename iterator_traits<_InputIterator1>::value_type>) 05361 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05362 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05363 05364 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 05365 __first2, __last2, __result, 05366 __gnu_cxx::__ops::__iter_less_iter()); 05367 } 05368 05369 /** 05370 * @brief Return the symmetric difference of two sorted ranges using 05371 * comparison functor. 05372 * @ingroup set_algorithms 05373 * @param __first1 Start of first range. 05374 * @param __last1 End of first range. 05375 * @param __first2 Start of second range. 05376 * @param __last2 End of second range. 05377 * @param __comp The comparison functor. 05378 * @return End of the output range. 05379 * @ingroup set_algorithms 05380 * 05381 * This operation iterates over both ranges, copying elements present in 05382 * one range but not the other in order to the output range. Iterators 05383 * increment for each range. When the current element of one range is less 05384 * than the other according to @p comp, that element is copied and the 05385 * iterator advances. If an element is contained in both ranges according 05386 * to @p __comp, no elements are copied and both ranges advance. The output 05387 * range may not overlap either input range. 05388 */ 05389 template<typename _InputIterator1, typename _InputIterator2, 05390 typename _OutputIterator, typename _Compare> 05391 inline _OutputIterator 05392 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05393 _InputIterator2 __first2, _InputIterator2 __last2, 05394 _OutputIterator __result, 05395 _Compare __comp) 05396 { 05397 // concept requirements 05398 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05399 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05400 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05401 typename iterator_traits<_InputIterator1>::value_type>) 05402 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05403 typename iterator_traits<_InputIterator2>::value_type>) 05404 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05405 typename iterator_traits<_InputIterator1>::value_type, 05406 typename iterator_traits<_InputIterator2>::value_type>) 05407 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05408 typename iterator_traits<_InputIterator2>::value_type, 05409 typename iterator_traits<_InputIterator1>::value_type>) 05410 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05411 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05412 05413 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 05414 __first2, __last2, __result, 05415 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05416 } 05417 05418 template<typename _ForwardIterator, typename _Compare> 05419 _GLIBCXX14_CONSTEXPR 05420 _ForwardIterator 05421 __min_element(_ForwardIterator __first, _ForwardIterator __last, 05422 _Compare __comp) 05423 { 05424 if (__first == __last) 05425 return __first; 05426 _ForwardIterator __result = __first; 05427 while (++__first != __last) 05428 if (__comp(__first, __result)) 05429 __result = __first; 05430 return __result; 05431 } 05432 05433 /** 05434 * @brief Return the minimum element in a range. 05435 * @ingroup sorting_algorithms 05436 * @param __first Start of range. 05437 * @param __last End of range. 05438 * @return Iterator referencing the first instance of the smallest value. 05439 */ 05440 template<typename _ForwardIterator> 05441 _GLIBCXX14_CONSTEXPR 05442 _ForwardIterator 05443 inline min_element(_ForwardIterator __first, _ForwardIterator __last) 05444 { 05445 // concept requirements 05446 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05447 __glibcxx_function_requires(_LessThanComparableConcept< 05448 typename iterator_traits<_ForwardIterator>::value_type>) 05449 __glibcxx_requires_valid_range(__first, __last); 05450 05451 return _GLIBCXX_STD_A::__min_element(__first, __last, 05452 __gnu_cxx::__ops::__iter_less_iter()); 05453 } 05454 05455 /** 05456 * @brief Return the minimum element in a range using comparison functor. 05457 * @ingroup sorting_algorithms 05458 * @param __first Start of range. 05459 * @param __last End of range. 05460 * @param __comp Comparison functor. 05461 * @return Iterator referencing the first instance of the smallest value 05462 * according to __comp. 05463 */ 05464 template<typename _ForwardIterator, typename _Compare> 05465 _GLIBCXX14_CONSTEXPR 05466 inline _ForwardIterator 05467 min_element(_ForwardIterator __first, _ForwardIterator __last, 05468 _Compare __comp) 05469 { 05470 // concept requirements 05471 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05472 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05473 typename iterator_traits<_ForwardIterator>::value_type, 05474 typename iterator_traits<_ForwardIterator>::value_type>) 05475 __glibcxx_requires_valid_range(__first, __last); 05476 05477 return _GLIBCXX_STD_A::__min_element(__first, __last, 05478 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05479 } 05480 05481 template<typename _ForwardIterator, typename _Compare> 05482 _GLIBCXX14_CONSTEXPR 05483 _ForwardIterator 05484 __max_element(_ForwardIterator __first, _ForwardIterator __last, 05485 _Compare __comp) 05486 { 05487 if (__first == __last) return __first; 05488 _ForwardIterator __result = __first; 05489 while (++__first != __last) 05490 if (__comp(__result, __first)) 05491 __result = __first; 05492 return __result; 05493 } 05494 05495 /** 05496 * @brief Return the maximum element in a range. 05497 * @ingroup sorting_algorithms 05498 * @param __first Start of range. 05499 * @param __last End of range. 05500 * @return Iterator referencing the first instance of the largest value. 05501 */ 05502 template<typename _ForwardIterator> 05503 _GLIBCXX14_CONSTEXPR 05504 inline _ForwardIterator 05505 max_element(_ForwardIterator __first, _ForwardIterator __last) 05506 { 05507 // concept requirements 05508 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05509 __glibcxx_function_requires(_LessThanComparableConcept< 05510 typename iterator_traits<_ForwardIterator>::value_type>) 05511 __glibcxx_requires_valid_range(__first, __last); 05512 05513 return _GLIBCXX_STD_A::__max_element(__first, __last, 05514 __gnu_cxx::__ops::__iter_less_iter()); 05515 } 05516 05517 /** 05518 * @brief Return the maximum element in a range using comparison functor. 05519 * @ingroup sorting_algorithms 05520 * @param __first Start of range. 05521 * @param __last End of range. 05522 * @param __comp Comparison functor. 05523 * @return Iterator referencing the first instance of the largest value 05524 * according to __comp. 05525 */ 05526 template<typename _ForwardIterator, typename _Compare> 05527 _GLIBCXX14_CONSTEXPR 05528 inline _ForwardIterator 05529 max_element(_ForwardIterator __first, _ForwardIterator __last, 05530 _Compare __comp) 05531 { 05532 // concept requirements 05533 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05534 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05535 typename iterator_traits<_ForwardIterator>::value_type, 05536 typename iterator_traits<_ForwardIterator>::value_type>) 05537 __glibcxx_requires_valid_range(__first, __last); 05538 05539 return _GLIBCXX_STD_A::__max_element(__first, __last, 05540 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05541 } 05542 05543 _GLIBCXX_END_NAMESPACE_ALGO 05544 } // namespace std 05545 05546 #endif /* _STL_ALGO_H */