libstdc++
|
00001 // Algorithm implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2016 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 #ifdef _GLIBCXX_CONCEPT_CHECKS 01739 typedef typename iterator_traits<_InputIterator>::value_type 01740 _InputValueType; 01741 typedef typename iterator_traits<_RandomAccessIterator>::value_type 01742 _OutputValueType; 01743 #endif 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_irreflexive(__first, __last); 01754 __glibcxx_requires_valid_range(__result_first, __result_last); 01755 01756 return std::__partial_sort_copy(__first, __last, 01757 __result_first, __result_last, 01758 __gnu_cxx::__ops::__iter_less_iter()); 01759 } 01760 01761 /** 01762 * @brief Copy the smallest elements of a sequence using a predicate for 01763 * comparison. 01764 * @ingroup sorting_algorithms 01765 * @param __first An input iterator. 01766 * @param __last Another input iterator. 01767 * @param __result_first A random-access iterator. 01768 * @param __result_last Another random-access iterator. 01769 * @param __comp A comparison functor. 01770 * @return An iterator indicating the end of the resulting sequence. 01771 * 01772 * Copies and sorts the smallest N values from the range @p [__first,__last) 01773 * to the range beginning at @p result_first, where the number of 01774 * elements to be copied, @p N, is the smaller of @p (__last-__first) and 01775 * @p (__result_last-__result_first). 01776 * After the sort if @e i and @e j are iterators in the range 01777 * @p [__result_first,__result_first+N) such that i precedes j then 01778 * @p __comp(*j,*i) is false. 01779 * The value returned is @p __result_first+N. 01780 */ 01781 template<typename _InputIterator, typename _RandomAccessIterator, 01782 typename _Compare> 01783 inline _RandomAccessIterator 01784 partial_sort_copy(_InputIterator __first, _InputIterator __last, 01785 _RandomAccessIterator __result_first, 01786 _RandomAccessIterator __result_last, 01787 _Compare __comp) 01788 { 01789 #ifdef _GLIBCXX_CONCEPT_CHECKS 01790 typedef typename iterator_traits<_InputIterator>::value_type 01791 _InputValueType; 01792 typedef typename iterator_traits<_RandomAccessIterator>::value_type 01793 _OutputValueType; 01794 #endif 01795 01796 // concept requirements 01797 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 01798 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 01799 _RandomAccessIterator>) 01800 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 01801 _OutputValueType>) 01802 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 01803 _InputValueType, _OutputValueType>) 01804 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 01805 _OutputValueType, _OutputValueType>) 01806 __glibcxx_requires_valid_range(__first, __last); 01807 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 01808 __glibcxx_requires_valid_range(__result_first, __result_last); 01809 01810 return std::__partial_sort_copy(__first, __last, 01811 __result_first, __result_last, 01812 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 01813 } 01814 01815 /// This is a helper function for the sort routine. 01816 template<typename _RandomAccessIterator, typename _Compare> 01817 void 01818 __unguarded_linear_insert(_RandomAccessIterator __last, 01819 _Compare __comp) 01820 { 01821 typename iterator_traits<_RandomAccessIterator>::value_type 01822 __val = _GLIBCXX_MOVE(*__last); 01823 _RandomAccessIterator __next = __last; 01824 --__next; 01825 while (__comp(__val, __next)) 01826 { 01827 *__last = _GLIBCXX_MOVE(*__next); 01828 __last = __next; 01829 --__next; 01830 } 01831 *__last = _GLIBCXX_MOVE(__val); 01832 } 01833 01834 /// This is a helper function for the sort routine. 01835 template<typename _RandomAccessIterator, typename _Compare> 01836 void 01837 __insertion_sort(_RandomAccessIterator __first, 01838 _RandomAccessIterator __last, _Compare __comp) 01839 { 01840 if (__first == __last) return; 01841 01842 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 01843 { 01844 if (__comp(__i, __first)) 01845 { 01846 typename iterator_traits<_RandomAccessIterator>::value_type 01847 __val = _GLIBCXX_MOVE(*__i); 01848 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); 01849 *__first = _GLIBCXX_MOVE(__val); 01850 } 01851 else 01852 std::__unguarded_linear_insert(__i, 01853 __gnu_cxx::__ops::__val_comp_iter(__comp)); 01854 } 01855 } 01856 01857 /// This is a helper function for the sort routine. 01858 template<typename _RandomAccessIterator, typename _Compare> 01859 inline void 01860 __unguarded_insertion_sort(_RandomAccessIterator __first, 01861 _RandomAccessIterator __last, _Compare __comp) 01862 { 01863 for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 01864 std::__unguarded_linear_insert(__i, 01865 __gnu_cxx::__ops::__val_comp_iter(__comp)); 01866 } 01867 01868 /** 01869 * @doctodo 01870 * This controls some aspect of the sort routines. 01871 */ 01872 enum { _S_threshold = 16 }; 01873 01874 /// This is a helper function for the sort routine. 01875 template<typename _RandomAccessIterator, typename _Compare> 01876 void 01877 __final_insertion_sort(_RandomAccessIterator __first, 01878 _RandomAccessIterator __last, _Compare __comp) 01879 { 01880 if (__last - __first > int(_S_threshold)) 01881 { 01882 std::__insertion_sort(__first, __first + int(_S_threshold), __comp); 01883 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, 01884 __comp); 01885 } 01886 else 01887 std::__insertion_sort(__first, __last, __comp); 01888 } 01889 01890 /// This is a helper function... 01891 template<typename _RandomAccessIterator, typename _Compare> 01892 _RandomAccessIterator 01893 __unguarded_partition(_RandomAccessIterator __first, 01894 _RandomAccessIterator __last, 01895 _RandomAccessIterator __pivot, _Compare __comp) 01896 { 01897 while (true) 01898 { 01899 while (__comp(__first, __pivot)) 01900 ++__first; 01901 --__last; 01902 while (__comp(__pivot, __last)) 01903 --__last; 01904 if (!(__first < __last)) 01905 return __first; 01906 std::iter_swap(__first, __last); 01907 ++__first; 01908 } 01909 } 01910 01911 /// This is a helper function... 01912 template<typename _RandomAccessIterator, typename _Compare> 01913 inline _RandomAccessIterator 01914 __unguarded_partition_pivot(_RandomAccessIterator __first, 01915 _RandomAccessIterator __last, _Compare __comp) 01916 { 01917 _RandomAccessIterator __mid = __first + (__last - __first) / 2; 01918 std::__move_median_to_first(__first, __first + 1, __mid, __last - 1, 01919 __comp); 01920 return std::__unguarded_partition(__first + 1, __last, __first, __comp); 01921 } 01922 01923 template<typename _RandomAccessIterator, typename _Compare> 01924 inline void 01925 __partial_sort(_RandomAccessIterator __first, 01926 _RandomAccessIterator __middle, 01927 _RandomAccessIterator __last, 01928 _Compare __comp) 01929 { 01930 std::__heap_select(__first, __middle, __last, __comp); 01931 std::__sort_heap(__first, __middle, __comp); 01932 } 01933 01934 /// This is a helper function for the sort routine. 01935 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 01936 void 01937 __introsort_loop(_RandomAccessIterator __first, 01938 _RandomAccessIterator __last, 01939 _Size __depth_limit, _Compare __comp) 01940 { 01941 while (__last - __first > int(_S_threshold)) 01942 { 01943 if (__depth_limit == 0) 01944 { 01945 std::__partial_sort(__first, __last, __last, __comp); 01946 return; 01947 } 01948 --__depth_limit; 01949 _RandomAccessIterator __cut = 01950 std::__unguarded_partition_pivot(__first, __last, __comp); 01951 std::__introsort_loop(__cut, __last, __depth_limit, __comp); 01952 __last = __cut; 01953 } 01954 } 01955 01956 // sort 01957 01958 template<typename _RandomAccessIterator, typename _Compare> 01959 inline void 01960 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 01961 _Compare __comp) 01962 { 01963 if (__first != __last) 01964 { 01965 std::__introsort_loop(__first, __last, 01966 std::__lg(__last - __first) * 2, 01967 __comp); 01968 std::__final_insertion_sort(__first, __last, __comp); 01969 } 01970 } 01971 01972 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 01973 void 01974 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, 01975 _RandomAccessIterator __last, _Size __depth_limit, 01976 _Compare __comp) 01977 { 01978 while (__last - __first > 3) 01979 { 01980 if (__depth_limit == 0) 01981 { 01982 std::__heap_select(__first, __nth + 1, __last, __comp); 01983 // Place the nth largest element in its final position. 01984 std::iter_swap(__first, __nth); 01985 return; 01986 } 01987 --__depth_limit; 01988 _RandomAccessIterator __cut = 01989 std::__unguarded_partition_pivot(__first, __last, __comp); 01990 if (__cut <= __nth) 01991 __first = __cut; 01992 else 01993 __last = __cut; 01994 } 01995 std::__insertion_sort(__first, __last, __comp); 01996 } 01997 01998 // nth_element 01999 02000 // lower_bound moved to stl_algobase.h 02001 02002 /** 02003 * @brief Finds the first position in which @p __val could be inserted 02004 * without changing the ordering. 02005 * @ingroup binary_search_algorithms 02006 * @param __first An iterator. 02007 * @param __last Another iterator. 02008 * @param __val The search term. 02009 * @param __comp A functor to use for comparisons. 02010 * @return An iterator pointing to the first element <em>not less 02011 * than</em> @p __val, or end() if every element is less 02012 * than @p __val. 02013 * @ingroup binary_search_algorithms 02014 * 02015 * The comparison function should have the same effects on ordering as 02016 * the function used for the initial sort. 02017 */ 02018 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02019 inline _ForwardIterator 02020 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 02021 const _Tp& __val, _Compare __comp) 02022 { 02023 // concept requirements 02024 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02025 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02026 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 02027 __glibcxx_requires_partitioned_lower_pred(__first, __last, 02028 __val, __comp); 02029 02030 return std::__lower_bound(__first, __last, __val, 02031 __gnu_cxx::__ops::__iter_comp_val(__comp)); 02032 } 02033 02034 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02035 _ForwardIterator 02036 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02037 const _Tp& __val, _Compare __comp) 02038 { 02039 typedef typename iterator_traits<_ForwardIterator>::difference_type 02040 _DistanceType; 02041 02042 _DistanceType __len = std::distance(__first, __last); 02043 02044 while (__len > 0) 02045 { 02046 _DistanceType __half = __len >> 1; 02047 _ForwardIterator __middle = __first; 02048 std::advance(__middle, __half); 02049 if (__comp(__val, __middle)) 02050 __len = __half; 02051 else 02052 { 02053 __first = __middle; 02054 ++__first; 02055 __len = __len - __half - 1; 02056 } 02057 } 02058 return __first; 02059 } 02060 02061 /** 02062 * @brief Finds the last position in which @p __val could be inserted 02063 * without changing the ordering. 02064 * @ingroup binary_search_algorithms 02065 * @param __first An iterator. 02066 * @param __last Another iterator. 02067 * @param __val The search term. 02068 * @return An iterator pointing to the first element greater than @p __val, 02069 * or end() if no elements are greater than @p __val. 02070 * @ingroup binary_search_algorithms 02071 */ 02072 template<typename _ForwardIterator, typename _Tp> 02073 inline _ForwardIterator 02074 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02075 const _Tp& __val) 02076 { 02077 // concept requirements 02078 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02079 __glibcxx_function_requires(_LessThanOpConcept< 02080 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 02081 __glibcxx_requires_partitioned_upper(__first, __last, __val); 02082 02083 return std::__upper_bound(__first, __last, __val, 02084 __gnu_cxx::__ops::__val_less_iter()); 02085 } 02086 02087 /** 02088 * @brief Finds the last position in which @p __val could be inserted 02089 * without changing the ordering. 02090 * @ingroup binary_search_algorithms 02091 * @param __first An iterator. 02092 * @param __last Another iterator. 02093 * @param __val The search term. 02094 * @param __comp A functor to use for comparisons. 02095 * @return An iterator pointing to the first element greater than @p __val, 02096 * or end() if no elements are greater than @p __val. 02097 * @ingroup binary_search_algorithms 02098 * 02099 * The comparison function should have the same effects on ordering as 02100 * the function used for the initial sort. 02101 */ 02102 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02103 inline _ForwardIterator 02104 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02105 const _Tp& __val, _Compare __comp) 02106 { 02107 // concept requirements 02108 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02109 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02110 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 02111 __glibcxx_requires_partitioned_upper_pred(__first, __last, 02112 __val, __comp); 02113 02114 return std::__upper_bound(__first, __last, __val, 02115 __gnu_cxx::__ops::__val_comp_iter(__comp)); 02116 } 02117 02118 template<typename _ForwardIterator, typename _Tp, 02119 typename _CompareItTp, typename _CompareTpIt> 02120 pair<_ForwardIterator, _ForwardIterator> 02121 __equal_range(_ForwardIterator __first, _ForwardIterator __last, 02122 const _Tp& __val, 02123 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it) 02124 { 02125 typedef typename iterator_traits<_ForwardIterator>::difference_type 02126 _DistanceType; 02127 02128 _DistanceType __len = std::distance(__first, __last); 02129 02130 while (__len > 0) 02131 { 02132 _DistanceType __half = __len >> 1; 02133 _ForwardIterator __middle = __first; 02134 std::advance(__middle, __half); 02135 if (__comp_it_val(__middle, __val)) 02136 { 02137 __first = __middle; 02138 ++__first; 02139 __len = __len - __half - 1; 02140 } 02141 else if (__comp_val_it(__val, __middle)) 02142 __len = __half; 02143 else 02144 { 02145 _ForwardIterator __left 02146 = std::__lower_bound(__first, __middle, __val, __comp_it_val); 02147 std::advance(__first, __len); 02148 _ForwardIterator __right 02149 = std::__upper_bound(++__middle, __first, __val, __comp_val_it); 02150 return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 02151 } 02152 } 02153 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 02154 } 02155 02156 /** 02157 * @brief Finds the largest subrange in which @p __val could be inserted 02158 * at any place in it without changing the ordering. 02159 * @ingroup binary_search_algorithms 02160 * @param __first An iterator. 02161 * @param __last Another iterator. 02162 * @param __val The search term. 02163 * @return An pair of iterators defining the subrange. 02164 * @ingroup binary_search_algorithms 02165 * 02166 * This is equivalent to 02167 * @code 02168 * std::make_pair(lower_bound(__first, __last, __val), 02169 * upper_bound(__first, __last, __val)) 02170 * @endcode 02171 * but does not actually call those functions. 02172 */ 02173 template<typename _ForwardIterator, typename _Tp> 02174 inline pair<_ForwardIterator, _ForwardIterator> 02175 equal_range(_ForwardIterator __first, _ForwardIterator __last, 02176 const _Tp& __val) 02177 { 02178 // concept requirements 02179 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02180 __glibcxx_function_requires(_LessThanOpConcept< 02181 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 02182 __glibcxx_function_requires(_LessThanOpConcept< 02183 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 02184 __glibcxx_requires_partitioned_lower(__first, __last, __val); 02185 __glibcxx_requires_partitioned_upper(__first, __last, __val); 02186 02187 return std::__equal_range(__first, __last, __val, 02188 __gnu_cxx::__ops::__iter_less_val(), 02189 __gnu_cxx::__ops::__val_less_iter()); 02190 } 02191 02192 /** 02193 * @brief Finds the largest subrange in which @p __val could be inserted 02194 * at any place in it without changing the ordering. 02195 * @param __first An iterator. 02196 * @param __last Another iterator. 02197 * @param __val The search term. 02198 * @param __comp A functor to use for comparisons. 02199 * @return An pair of iterators defining the subrange. 02200 * @ingroup binary_search_algorithms 02201 * 02202 * This is equivalent to 02203 * @code 02204 * std::make_pair(lower_bound(__first, __last, __val, __comp), 02205 * upper_bound(__first, __last, __val, __comp)) 02206 * @endcode 02207 * but does not actually call those functions. 02208 */ 02209 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02210 inline pair<_ForwardIterator, _ForwardIterator> 02211 equal_range(_ForwardIterator __first, _ForwardIterator __last, 02212 const _Tp& __val, _Compare __comp) 02213 { 02214 // concept requirements 02215 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02216 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02217 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 02218 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02219 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 02220 __glibcxx_requires_partitioned_lower_pred(__first, __last, 02221 __val, __comp); 02222 __glibcxx_requires_partitioned_upper_pred(__first, __last, 02223 __val, __comp); 02224 02225 return std::__equal_range(__first, __last, __val, 02226 __gnu_cxx::__ops::__iter_comp_val(__comp), 02227 __gnu_cxx::__ops::__val_comp_iter(__comp)); 02228 } 02229 02230 /** 02231 * @brief Determines whether an element exists in a range. 02232 * @ingroup binary_search_algorithms 02233 * @param __first An iterator. 02234 * @param __last Another iterator. 02235 * @param __val The search term. 02236 * @return True if @p __val (or its equivalent) is in [@p 02237 * __first,@p __last ]. 02238 * 02239 * Note that this does not actually return an iterator to @p __val. For 02240 * that, use std::find or a container's specialized find member functions. 02241 */ 02242 template<typename _ForwardIterator, typename _Tp> 02243 bool 02244 binary_search(_ForwardIterator __first, _ForwardIterator __last, 02245 const _Tp& __val) 02246 { 02247 // concept requirements 02248 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02249 __glibcxx_function_requires(_LessThanOpConcept< 02250 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 02251 __glibcxx_requires_partitioned_lower(__first, __last, __val); 02252 __glibcxx_requires_partitioned_upper(__first, __last, __val); 02253 02254 _ForwardIterator __i 02255 = std::__lower_bound(__first, __last, __val, 02256 __gnu_cxx::__ops::__iter_less_val()); 02257 return __i != __last && !(__val < *__i); 02258 } 02259 02260 /** 02261 * @brief Determines whether an element exists in a range. 02262 * @ingroup binary_search_algorithms 02263 * @param __first An iterator. 02264 * @param __last Another iterator. 02265 * @param __val The search term. 02266 * @param __comp A functor to use for comparisons. 02267 * @return True if @p __val (or its equivalent) is in @p [__first,__last]. 02268 * 02269 * Note that this does not actually return an iterator to @p __val. For 02270 * that, use std::find or a container's specialized find member functions. 02271 * 02272 * The comparison function should have the same effects on ordering as 02273 * the function used for the initial sort. 02274 */ 02275 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02276 bool 02277 binary_search(_ForwardIterator __first, _ForwardIterator __last, 02278 const _Tp& __val, _Compare __comp) 02279 { 02280 // concept requirements 02281 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02282 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02283 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 02284 __glibcxx_requires_partitioned_lower_pred(__first, __last, 02285 __val, __comp); 02286 __glibcxx_requires_partitioned_upper_pred(__first, __last, 02287 __val, __comp); 02288 02289 _ForwardIterator __i 02290 = std::__lower_bound(__first, __last, __val, 02291 __gnu_cxx::__ops::__iter_comp_val(__comp)); 02292 return __i != __last && !bool(__comp(__val, *__i)); 02293 } 02294 02295 // merge 02296 02297 /// This is a helper function for the __merge_adaptive routines. 02298 template<typename _InputIterator1, typename _InputIterator2, 02299 typename _OutputIterator, typename _Compare> 02300 void 02301 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, 02302 _InputIterator2 __first2, _InputIterator2 __last2, 02303 _OutputIterator __result, _Compare __comp) 02304 { 02305 while (__first1 != __last1 && __first2 != __last2) 02306 { 02307 if (__comp(__first2, __first1)) 02308 { 02309 *__result = _GLIBCXX_MOVE(*__first2); 02310 ++__first2; 02311 } 02312 else 02313 { 02314 *__result = _GLIBCXX_MOVE(*__first1); 02315 ++__first1; 02316 } 02317 ++__result; 02318 } 02319 if (__first1 != __last1) 02320 _GLIBCXX_MOVE3(__first1, __last1, __result); 02321 } 02322 02323 /// This is a helper function for the __merge_adaptive routines. 02324 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 02325 typename _BidirectionalIterator3, typename _Compare> 02326 void 02327 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, 02328 _BidirectionalIterator1 __last1, 02329 _BidirectionalIterator2 __first2, 02330 _BidirectionalIterator2 __last2, 02331 _BidirectionalIterator3 __result, 02332 _Compare __comp) 02333 { 02334 if (__first1 == __last1) 02335 { 02336 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); 02337 return; 02338 } 02339 else if (__first2 == __last2) 02340 return; 02341 02342 --__last1; 02343 --__last2; 02344 while (true) 02345 { 02346 if (__comp(__last2, __last1)) 02347 { 02348 *--__result = _GLIBCXX_MOVE(*__last1); 02349 if (__first1 == __last1) 02350 { 02351 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); 02352 return; 02353 } 02354 --__last1; 02355 } 02356 else 02357 { 02358 *--__result = _GLIBCXX_MOVE(*__last2); 02359 if (__first2 == __last2) 02360 return; 02361 --__last2; 02362 } 02363 } 02364 } 02365 02366 /// This is a helper function for the merge routines. 02367 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 02368 typename _Distance> 02369 _BidirectionalIterator1 02370 __rotate_adaptive(_BidirectionalIterator1 __first, 02371 _BidirectionalIterator1 __middle, 02372 _BidirectionalIterator1 __last, 02373 _Distance __len1, _Distance __len2, 02374 _BidirectionalIterator2 __buffer, 02375 _Distance __buffer_size) 02376 { 02377 _BidirectionalIterator2 __buffer_end; 02378 if (__len1 > __len2 && __len2 <= __buffer_size) 02379 { 02380 if (__len2) 02381 { 02382 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 02383 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last); 02384 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first); 02385 } 02386 else 02387 return __first; 02388 } 02389 else if (__len1 <= __buffer_size) 02390 { 02391 if (__len1) 02392 { 02393 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 02394 _GLIBCXX_MOVE3(__middle, __last, __first); 02395 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last); 02396 } 02397 else 02398 return __last; 02399 } 02400 else 02401 { 02402 std::rotate(__first, __middle, __last); 02403 std::advance(__first, std::distance(__middle, __last)); 02404 return __first; 02405 } 02406 } 02407 02408 /// This is a helper function for the merge routines. 02409 template<typename _BidirectionalIterator, typename _Distance, 02410 typename _Pointer, typename _Compare> 02411 void 02412 __merge_adaptive(_BidirectionalIterator __first, 02413 _BidirectionalIterator __middle, 02414 _BidirectionalIterator __last, 02415 _Distance __len1, _Distance __len2, 02416 _Pointer __buffer, _Distance __buffer_size, 02417 _Compare __comp) 02418 { 02419 if (__len1 <= __len2 && __len1 <= __buffer_size) 02420 { 02421 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 02422 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, 02423 __first, __comp); 02424 } 02425 else if (__len2 <= __buffer_size) 02426 { 02427 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 02428 std::__move_merge_adaptive_backward(__first, __middle, __buffer, 02429 __buffer_end, __last, __comp); 02430 } 02431 else 02432 { 02433 _BidirectionalIterator __first_cut = __first; 02434 _BidirectionalIterator __second_cut = __middle; 02435 _Distance __len11 = 0; 02436 _Distance __len22 = 0; 02437 if (__len1 > __len2) 02438 { 02439 __len11 = __len1 / 2; 02440 std::advance(__first_cut, __len11); 02441 __second_cut 02442 = std::__lower_bound(__middle, __last, *__first_cut, 02443 __gnu_cxx::__ops::__iter_comp_val(__comp)); 02444 __len22 = std::distance(__middle, __second_cut); 02445 } 02446 else 02447 { 02448 __len22 = __len2 / 2; 02449 std::advance(__second_cut, __len22); 02450 __first_cut 02451 = std::__upper_bound(__first, __middle, *__second_cut, 02452 __gnu_cxx::__ops::__val_comp_iter(__comp)); 02453 __len11 = std::distance(__first, __first_cut); 02454 } 02455 02456 _BidirectionalIterator __new_middle 02457 = std::__rotate_adaptive(__first_cut, __middle, __second_cut, 02458 __len1 - __len11, __len22, __buffer, 02459 __buffer_size); 02460 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 02461 __len22, __buffer, __buffer_size, __comp); 02462 std::__merge_adaptive(__new_middle, __second_cut, __last, 02463 __len1 - __len11, 02464 __len2 - __len22, __buffer, 02465 __buffer_size, __comp); 02466 } 02467 } 02468 02469 /// This is a helper function for the merge routines. 02470 template<typename _BidirectionalIterator, typename _Distance, 02471 typename _Compare> 02472 void 02473 __merge_without_buffer(_BidirectionalIterator __first, 02474 _BidirectionalIterator __middle, 02475 _BidirectionalIterator __last, 02476 _Distance __len1, _Distance __len2, 02477 _Compare __comp) 02478 { 02479 if (__len1 == 0 || __len2 == 0) 02480 return; 02481 02482 if (__len1 + __len2 == 2) 02483 { 02484 if (__comp(__middle, __first)) 02485 std::iter_swap(__first, __middle); 02486 return; 02487 } 02488 02489 _BidirectionalIterator __first_cut = __first; 02490 _BidirectionalIterator __second_cut = __middle; 02491 _Distance __len11 = 0; 02492 _Distance __len22 = 0; 02493 if (__len1 > __len2) 02494 { 02495 __len11 = __len1 / 2; 02496 std::advance(__first_cut, __len11); 02497 __second_cut 02498 = std::__lower_bound(__middle, __last, *__first_cut, 02499 __gnu_cxx::__ops::__iter_comp_val(__comp)); 02500 __len22 = std::distance(__middle, __second_cut); 02501 } 02502 else 02503 { 02504 __len22 = __len2 / 2; 02505 std::advance(__second_cut, __len22); 02506 __first_cut 02507 = std::__upper_bound(__first, __middle, *__second_cut, 02508 __gnu_cxx::__ops::__val_comp_iter(__comp)); 02509 __len11 = std::distance(__first, __first_cut); 02510 } 02511 02512 std::rotate(__first_cut, __middle, __second_cut); 02513 _BidirectionalIterator __new_middle = __first_cut; 02514 std::advance(__new_middle, std::distance(__middle, __second_cut)); 02515 std::__merge_without_buffer(__first, __first_cut, __new_middle, 02516 __len11, __len22, __comp); 02517 std::__merge_without_buffer(__new_middle, __second_cut, __last, 02518 __len1 - __len11, __len2 - __len22, __comp); 02519 } 02520 02521 template<typename _BidirectionalIterator, typename _Compare> 02522 void 02523 __inplace_merge(_BidirectionalIterator __first, 02524 _BidirectionalIterator __middle, 02525 _BidirectionalIterator __last, 02526 _Compare __comp) 02527 { 02528 typedef typename iterator_traits<_BidirectionalIterator>::value_type 02529 _ValueType; 02530 typedef typename iterator_traits<_BidirectionalIterator>::difference_type 02531 _DistanceType; 02532 02533 if (__first == __middle || __middle == __last) 02534 return; 02535 02536 const _DistanceType __len1 = std::distance(__first, __middle); 02537 const _DistanceType __len2 = std::distance(__middle, __last); 02538 02539 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf; 02540 _TmpBuf __buf(__first, __last); 02541 02542 if (__buf.begin() == 0) 02543 std::__merge_without_buffer 02544 (__first, __middle, __last, __len1, __len2, __comp); 02545 else 02546 std::__merge_adaptive 02547 (__first, __middle, __last, __len1, __len2, __buf.begin(), 02548 _DistanceType(__buf.size()), __comp); 02549 } 02550 02551 /** 02552 * @brief Merges two sorted ranges in place. 02553 * @ingroup sorting_algorithms 02554 * @param __first An iterator. 02555 * @param __middle Another iterator. 02556 * @param __last Another iterator. 02557 * @return Nothing. 02558 * 02559 * Merges two sorted and consecutive ranges, [__first,__middle) and 02560 * [__middle,__last), and puts the result in [__first,__last). The 02561 * output will be sorted. The sort is @e stable, that is, for 02562 * equivalent elements in the two ranges, elements from the first 02563 * range will always come before elements from the second. 02564 * 02565 * If enough additional memory is available, this takes (__last-__first)-1 02566 * comparisons. Otherwise an NlogN algorithm is used, where N is 02567 * distance(__first,__last). 02568 */ 02569 template<typename _BidirectionalIterator> 02570 inline void 02571 inplace_merge(_BidirectionalIterator __first, 02572 _BidirectionalIterator __middle, 02573 _BidirectionalIterator __last) 02574 { 02575 // concept requirements 02576 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 02577 _BidirectionalIterator>) 02578 __glibcxx_function_requires(_LessThanComparableConcept< 02579 typename iterator_traits<_BidirectionalIterator>::value_type>) 02580 __glibcxx_requires_sorted(__first, __middle); 02581 __glibcxx_requires_sorted(__middle, __last); 02582 __glibcxx_requires_irreflexive(__first, __last); 02583 02584 std::__inplace_merge(__first, __middle, __last, 02585 __gnu_cxx::__ops::__iter_less_iter()); 02586 } 02587 02588 /** 02589 * @brief Merges two sorted ranges in place. 02590 * @ingroup sorting_algorithms 02591 * @param __first An iterator. 02592 * @param __middle Another iterator. 02593 * @param __last Another iterator. 02594 * @param __comp A functor to use for comparisons. 02595 * @return Nothing. 02596 * 02597 * Merges two sorted and consecutive ranges, [__first,__middle) and 02598 * [middle,last), and puts the result in [__first,__last). The output will 02599 * be sorted. The sort is @e stable, that is, for equivalent 02600 * elements in the two ranges, elements from the first range will always 02601 * come before elements from the second. 02602 * 02603 * If enough additional memory is available, this takes (__last-__first)-1 02604 * comparisons. Otherwise an NlogN algorithm is used, where N is 02605 * distance(__first,__last). 02606 * 02607 * The comparison function should have the same effects on ordering as 02608 * the function used for the initial sort. 02609 */ 02610 template<typename _BidirectionalIterator, typename _Compare> 02611 inline void 02612 inplace_merge(_BidirectionalIterator __first, 02613 _BidirectionalIterator __middle, 02614 _BidirectionalIterator __last, 02615 _Compare __comp) 02616 { 02617 // concept requirements 02618 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 02619 _BidirectionalIterator>) 02620 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02621 typename iterator_traits<_BidirectionalIterator>::value_type, 02622 typename iterator_traits<_BidirectionalIterator>::value_type>) 02623 __glibcxx_requires_sorted_pred(__first, __middle, __comp); 02624 __glibcxx_requires_sorted_pred(__middle, __last, __comp); 02625 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 02626 02627 std::__inplace_merge(__first, __middle, __last, 02628 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 02629 } 02630 02631 02632 /// This is a helper function for the __merge_sort_loop routines. 02633 template<typename _InputIterator, typename _OutputIterator, 02634 typename _Compare> 02635 _OutputIterator 02636 __move_merge(_InputIterator __first1, _InputIterator __last1, 02637 _InputIterator __first2, _InputIterator __last2, 02638 _OutputIterator __result, _Compare __comp) 02639 { 02640 while (__first1 != __last1 && __first2 != __last2) 02641 { 02642 if (__comp(__first2, __first1)) 02643 { 02644 *__result = _GLIBCXX_MOVE(*__first2); 02645 ++__first2; 02646 } 02647 else 02648 { 02649 *__result = _GLIBCXX_MOVE(*__first1); 02650 ++__first1; 02651 } 02652 ++__result; 02653 } 02654 return _GLIBCXX_MOVE3(__first2, __last2, 02655 _GLIBCXX_MOVE3(__first1, __last1, 02656 __result)); 02657 } 02658 02659 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 02660 typename _Distance, typename _Compare> 02661 void 02662 __merge_sort_loop(_RandomAccessIterator1 __first, 02663 _RandomAccessIterator1 __last, 02664 _RandomAccessIterator2 __result, _Distance __step_size, 02665 _Compare __comp) 02666 { 02667 const _Distance __two_step = 2 * __step_size; 02668 02669 while (__last - __first >= __two_step) 02670 { 02671 __result = std::__move_merge(__first, __first + __step_size, 02672 __first + __step_size, 02673 __first + __two_step, 02674 __result, __comp); 02675 __first += __two_step; 02676 } 02677 __step_size = std::min(_Distance(__last - __first), __step_size); 02678 02679 std::__move_merge(__first, __first + __step_size, 02680 __first + __step_size, __last, __result, __comp); 02681 } 02682 02683 template<typename _RandomAccessIterator, typename _Distance, 02684 typename _Compare> 02685 void 02686 __chunk_insertion_sort(_RandomAccessIterator __first, 02687 _RandomAccessIterator __last, 02688 _Distance __chunk_size, _Compare __comp) 02689 { 02690 while (__last - __first >= __chunk_size) 02691 { 02692 std::__insertion_sort(__first, __first + __chunk_size, __comp); 02693 __first += __chunk_size; 02694 } 02695 std::__insertion_sort(__first, __last, __comp); 02696 } 02697 02698 enum { _S_chunk_size = 7 }; 02699 02700 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare> 02701 void 02702 __merge_sort_with_buffer(_RandomAccessIterator __first, 02703 _RandomAccessIterator __last, 02704 _Pointer __buffer, _Compare __comp) 02705 { 02706 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 02707 _Distance; 02708 02709 const _Distance __len = __last - __first; 02710 const _Pointer __buffer_last = __buffer + __len; 02711 02712 _Distance __step_size = _S_chunk_size; 02713 std::__chunk_insertion_sort(__first, __last, __step_size, __comp); 02714 02715 while (__step_size < __len) 02716 { 02717 std::__merge_sort_loop(__first, __last, __buffer, 02718 __step_size, __comp); 02719 __step_size *= 2; 02720 std::__merge_sort_loop(__buffer, __buffer_last, __first, 02721 __step_size, __comp); 02722 __step_size *= 2; 02723 } 02724 } 02725 02726 template<typename _RandomAccessIterator, typename _Pointer, 02727 typename _Distance, typename _Compare> 02728 void 02729 __stable_sort_adaptive(_RandomAccessIterator __first, 02730 _RandomAccessIterator __last, 02731 _Pointer __buffer, _Distance __buffer_size, 02732 _Compare __comp) 02733 { 02734 const _Distance __len = (__last - __first + 1) / 2; 02735 const _RandomAccessIterator __middle = __first + __len; 02736 if (__len > __buffer_size) 02737 { 02738 std::__stable_sort_adaptive(__first, __middle, __buffer, 02739 __buffer_size, __comp); 02740 std::__stable_sort_adaptive(__middle, __last, __buffer, 02741 __buffer_size, __comp); 02742 } 02743 else 02744 { 02745 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); 02746 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); 02747 } 02748 std::__merge_adaptive(__first, __middle, __last, 02749 _Distance(__middle - __first), 02750 _Distance(__last - __middle), 02751 __buffer, __buffer_size, 02752 __comp); 02753 } 02754 02755 /// This is a helper function for the stable sorting routines. 02756 template<typename _RandomAccessIterator, typename _Compare> 02757 void 02758 __inplace_stable_sort(_RandomAccessIterator __first, 02759 _RandomAccessIterator __last, _Compare __comp) 02760 { 02761 if (__last - __first < 15) 02762 { 02763 std::__insertion_sort(__first, __last, __comp); 02764 return; 02765 } 02766 _RandomAccessIterator __middle = __first + (__last - __first) / 2; 02767 std::__inplace_stable_sort(__first, __middle, __comp); 02768 std::__inplace_stable_sort(__middle, __last, __comp); 02769 std::__merge_without_buffer(__first, __middle, __last, 02770 __middle - __first, 02771 __last - __middle, 02772 __comp); 02773 } 02774 02775 // stable_sort 02776 02777 // Set algorithms: includes, set_union, set_intersection, set_difference, 02778 // set_symmetric_difference. All of these algorithms have the precondition 02779 // that their input ranges are sorted and the postcondition that their output 02780 // ranges are sorted. 02781 02782 template<typename _InputIterator1, typename _InputIterator2, 02783 typename _Compare> 02784 bool 02785 __includes(_InputIterator1 __first1, _InputIterator1 __last1, 02786 _InputIterator2 __first2, _InputIterator2 __last2, 02787 _Compare __comp) 02788 { 02789 while (__first1 != __last1 && __first2 != __last2) 02790 if (__comp(__first2, __first1)) 02791 return false; 02792 else if (__comp(__first1, __first2)) 02793 ++__first1; 02794 else 02795 { 02796 ++__first1; 02797 ++__first2; 02798 } 02799 02800 return __first2 == __last2; 02801 } 02802 02803 /** 02804 * @brief Determines whether all elements of a sequence exists in a range. 02805 * @param __first1 Start of search range. 02806 * @param __last1 End of search range. 02807 * @param __first2 Start of sequence 02808 * @param __last2 End of sequence. 02809 * @return True if each element in [__first2,__last2) is contained in order 02810 * within [__first1,__last1). False otherwise. 02811 * @ingroup set_algorithms 02812 * 02813 * This operation expects both [__first1,__last1) and 02814 * [__first2,__last2) to be sorted. Searches for the presence of 02815 * each element in [__first2,__last2) within [__first1,__last1). 02816 * The iterators over each range only move forward, so this is a 02817 * linear algorithm. If an element in [__first2,__last2) is not 02818 * found before the search iterator reaches @p __last2, false is 02819 * returned. 02820 */ 02821 template<typename _InputIterator1, typename _InputIterator2> 02822 inline bool 02823 includes(_InputIterator1 __first1, _InputIterator1 __last1, 02824 _InputIterator2 __first2, _InputIterator2 __last2) 02825 { 02826 // concept requirements 02827 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 02828 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 02829 __glibcxx_function_requires(_LessThanOpConcept< 02830 typename iterator_traits<_InputIterator1>::value_type, 02831 typename iterator_traits<_InputIterator2>::value_type>) 02832 __glibcxx_function_requires(_LessThanOpConcept< 02833 typename iterator_traits<_InputIterator2>::value_type, 02834 typename iterator_traits<_InputIterator1>::value_type>) 02835 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 02836 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 02837 __glibcxx_requires_irreflexive2(__first1, __last1); 02838 __glibcxx_requires_irreflexive2(__first2, __last2); 02839 02840 return std::__includes(__first1, __last1, __first2, __last2, 02841 __gnu_cxx::__ops::__iter_less_iter()); 02842 } 02843 02844 /** 02845 * @brief Determines whether all elements of a sequence exists in a range 02846 * using comparison. 02847 * @ingroup set_algorithms 02848 * @param __first1 Start of search range. 02849 * @param __last1 End of search range. 02850 * @param __first2 Start of sequence 02851 * @param __last2 End of sequence. 02852 * @param __comp Comparison function to use. 02853 * @return True if each element in [__first2,__last2) is contained 02854 * in order within [__first1,__last1) according to comp. False 02855 * otherwise. @ingroup set_algorithms 02856 * 02857 * This operation expects both [__first1,__last1) and 02858 * [__first2,__last2) to be sorted. Searches for the presence of 02859 * each element in [__first2,__last2) within [__first1,__last1), 02860 * using comp to decide. The iterators over each range only move 02861 * forward, so this is a linear algorithm. If an element in 02862 * [__first2,__last2) is not found before the search iterator 02863 * reaches @p __last2, false is returned. 02864 */ 02865 template<typename _InputIterator1, typename _InputIterator2, 02866 typename _Compare> 02867 inline bool 02868 includes(_InputIterator1 __first1, _InputIterator1 __last1, 02869 _InputIterator2 __first2, _InputIterator2 __last2, 02870 _Compare __comp) 02871 { 02872 // concept requirements 02873 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 02874 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 02875 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02876 typename iterator_traits<_InputIterator1>::value_type, 02877 typename iterator_traits<_InputIterator2>::value_type>) 02878 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02879 typename iterator_traits<_InputIterator2>::value_type, 02880 typename iterator_traits<_InputIterator1>::value_type>) 02881 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 02882 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 02883 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 02884 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 02885 02886 return std::__includes(__first1, __last1, __first2, __last2, 02887 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 02888 } 02889 02890 // nth_element 02891 // merge 02892 // set_difference 02893 // set_intersection 02894 // set_union 02895 // stable_sort 02896 // set_symmetric_difference 02897 // min_element 02898 // max_element 02899 02900 template<typename _BidirectionalIterator, typename _Compare> 02901 bool 02902 __next_permutation(_BidirectionalIterator __first, 02903 _BidirectionalIterator __last, _Compare __comp) 02904 { 02905 if (__first == __last) 02906 return false; 02907 _BidirectionalIterator __i = __first; 02908 ++__i; 02909 if (__i == __last) 02910 return false; 02911 __i = __last; 02912 --__i; 02913 02914 for(;;) 02915 { 02916 _BidirectionalIterator __ii = __i; 02917 --__i; 02918 if (__comp(__i, __ii)) 02919 { 02920 _BidirectionalIterator __j = __last; 02921 while (!__comp(__i, --__j)) 02922 {} 02923 std::iter_swap(__i, __j); 02924 std::__reverse(__ii, __last, 02925 std::__iterator_category(__first)); 02926 return true; 02927 } 02928 if (__i == __first) 02929 { 02930 std::__reverse(__first, __last, 02931 std::__iterator_category(__first)); 02932 return false; 02933 } 02934 } 02935 } 02936 02937 /** 02938 * @brief Permute range into the next @e dictionary ordering. 02939 * @ingroup sorting_algorithms 02940 * @param __first Start of range. 02941 * @param __last End of range. 02942 * @return False if wrapped to first permutation, true otherwise. 02943 * 02944 * Treats all permutations of the range as a set of @e dictionary sorted 02945 * sequences. Permutes the current sequence into the next one of this set. 02946 * Returns true if there are more sequences to generate. If the sequence 02947 * is the largest of the set, the smallest is generated and false returned. 02948 */ 02949 template<typename _BidirectionalIterator> 02950 inline bool 02951 next_permutation(_BidirectionalIterator __first, 02952 _BidirectionalIterator __last) 02953 { 02954 // concept requirements 02955 __glibcxx_function_requires(_BidirectionalIteratorConcept< 02956 _BidirectionalIterator>) 02957 __glibcxx_function_requires(_LessThanComparableConcept< 02958 typename iterator_traits<_BidirectionalIterator>::value_type>) 02959 __glibcxx_requires_valid_range(__first, __last); 02960 __glibcxx_requires_irreflexive(__first, __last); 02961 02962 return std::__next_permutation 02963 (__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 02964 } 02965 02966 /** 02967 * @brief Permute range into the next @e dictionary ordering using 02968 * comparison functor. 02969 * @ingroup sorting_algorithms 02970 * @param __first Start of range. 02971 * @param __last End of range. 02972 * @param __comp A comparison functor. 02973 * @return False if wrapped to first permutation, true otherwise. 02974 * 02975 * Treats all permutations of the range [__first,__last) as a set of 02976 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current 02977 * sequence into the next one of this set. Returns true if there are more 02978 * sequences to generate. If the sequence is the largest of the set, the 02979 * smallest is generated and false returned. 02980 */ 02981 template<typename _BidirectionalIterator, typename _Compare> 02982 inline bool 02983 next_permutation(_BidirectionalIterator __first, 02984 _BidirectionalIterator __last, _Compare __comp) 02985 { 02986 // concept requirements 02987 __glibcxx_function_requires(_BidirectionalIteratorConcept< 02988 _BidirectionalIterator>) 02989 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02990 typename iterator_traits<_BidirectionalIterator>::value_type, 02991 typename iterator_traits<_BidirectionalIterator>::value_type>) 02992 __glibcxx_requires_valid_range(__first, __last); 02993 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 02994 02995 return std::__next_permutation 02996 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 02997 } 02998 02999 template<typename _BidirectionalIterator, typename _Compare> 03000 bool 03001 __prev_permutation(_BidirectionalIterator __first, 03002 _BidirectionalIterator __last, _Compare __comp) 03003 { 03004 if (__first == __last) 03005 return false; 03006 _BidirectionalIterator __i = __first; 03007 ++__i; 03008 if (__i == __last) 03009 return false; 03010 __i = __last; 03011 --__i; 03012 03013 for(;;) 03014 { 03015 _BidirectionalIterator __ii = __i; 03016 --__i; 03017 if (__comp(__ii, __i)) 03018 { 03019 _BidirectionalIterator __j = __last; 03020 while (!__comp(--__j, __i)) 03021 {} 03022 std::iter_swap(__i, __j); 03023 std::__reverse(__ii, __last, 03024 std::__iterator_category(__first)); 03025 return true; 03026 } 03027 if (__i == __first) 03028 { 03029 std::__reverse(__first, __last, 03030 std::__iterator_category(__first)); 03031 return false; 03032 } 03033 } 03034 } 03035 03036 /** 03037 * @brief Permute range into the previous @e dictionary ordering. 03038 * @ingroup sorting_algorithms 03039 * @param __first Start of range. 03040 * @param __last End of range. 03041 * @return False if wrapped to last permutation, true otherwise. 03042 * 03043 * Treats all permutations of the range as a set of @e dictionary sorted 03044 * sequences. Permutes the current sequence into the previous one of this 03045 * set. Returns true if there are more sequences to generate. If the 03046 * sequence is the smallest of the set, the largest is generated and false 03047 * returned. 03048 */ 03049 template<typename _BidirectionalIterator> 03050 inline bool 03051 prev_permutation(_BidirectionalIterator __first, 03052 _BidirectionalIterator __last) 03053 { 03054 // concept requirements 03055 __glibcxx_function_requires(_BidirectionalIteratorConcept< 03056 _BidirectionalIterator>) 03057 __glibcxx_function_requires(_LessThanComparableConcept< 03058 typename iterator_traits<_BidirectionalIterator>::value_type>) 03059 __glibcxx_requires_valid_range(__first, __last); 03060 __glibcxx_requires_irreflexive(__first, __last); 03061 03062 return std::__prev_permutation(__first, __last, 03063 __gnu_cxx::__ops::__iter_less_iter()); 03064 } 03065 03066 /** 03067 * @brief Permute range into the previous @e dictionary ordering using 03068 * comparison functor. 03069 * @ingroup sorting_algorithms 03070 * @param __first Start of range. 03071 * @param __last End of range. 03072 * @param __comp A comparison functor. 03073 * @return False if wrapped to last permutation, true otherwise. 03074 * 03075 * Treats all permutations of the range [__first,__last) as a set of 03076 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current 03077 * sequence into the previous one of this set. Returns true if there are 03078 * more sequences to generate. If the sequence is the smallest of the set, 03079 * the largest is generated and false returned. 03080 */ 03081 template<typename _BidirectionalIterator, typename _Compare> 03082 inline bool 03083 prev_permutation(_BidirectionalIterator __first, 03084 _BidirectionalIterator __last, _Compare __comp) 03085 { 03086 // concept requirements 03087 __glibcxx_function_requires(_BidirectionalIteratorConcept< 03088 _BidirectionalIterator>) 03089 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03090 typename iterator_traits<_BidirectionalIterator>::value_type, 03091 typename iterator_traits<_BidirectionalIterator>::value_type>) 03092 __glibcxx_requires_valid_range(__first, __last); 03093 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 03094 03095 return std::__prev_permutation(__first, __last, 03096 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 03097 } 03098 03099 // replace 03100 // replace_if 03101 03102 template<typename _InputIterator, typename _OutputIterator, 03103 typename _Predicate, typename _Tp> 03104 _OutputIterator 03105 __replace_copy_if(_InputIterator __first, _InputIterator __last, 03106 _OutputIterator __result, 03107 _Predicate __pred, const _Tp& __new_value) 03108 { 03109 for (; __first != __last; ++__first, (void)++__result) 03110 if (__pred(__first)) 03111 *__result = __new_value; 03112 else 03113 *__result = *__first; 03114 return __result; 03115 } 03116 03117 /** 03118 * @brief Copy a sequence, replacing each element of one value with another 03119 * value. 03120 * @param __first An input iterator. 03121 * @param __last An input iterator. 03122 * @param __result An output iterator. 03123 * @param __old_value The value to be replaced. 03124 * @param __new_value The replacement value. 03125 * @return The end of the output sequence, @p result+(last-first). 03126 * 03127 * Copies each element in the input range @p [__first,__last) to the 03128 * output range @p [__result,__result+(__last-__first)) replacing elements 03129 * equal to @p __old_value with @p __new_value. 03130 */ 03131 template<typename _InputIterator, typename _OutputIterator, typename _Tp> 03132 inline _OutputIterator 03133 replace_copy(_InputIterator __first, _InputIterator __last, 03134 _OutputIterator __result, 03135 const _Tp& __old_value, const _Tp& __new_value) 03136 { 03137 // concept requirements 03138 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03139 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 03140 typename iterator_traits<_InputIterator>::value_type>) 03141 __glibcxx_function_requires(_EqualOpConcept< 03142 typename iterator_traits<_InputIterator>::value_type, _Tp>) 03143 __glibcxx_requires_valid_range(__first, __last); 03144 03145 return std::__replace_copy_if(__first, __last, __result, 03146 __gnu_cxx::__ops::__iter_equals_val(__old_value), 03147 __new_value); 03148 } 03149 03150 /** 03151 * @brief Copy a sequence, replacing each value for which a predicate 03152 * returns true with another value. 03153 * @ingroup mutating_algorithms 03154 * @param __first An input iterator. 03155 * @param __last An input iterator. 03156 * @param __result An output iterator. 03157 * @param __pred A predicate. 03158 * @param __new_value The replacement value. 03159 * @return The end of the output sequence, @p __result+(__last-__first). 03160 * 03161 * Copies each element in the range @p [__first,__last) to the range 03162 * @p [__result,__result+(__last-__first)) replacing elements for which 03163 * @p __pred returns true with @p __new_value. 03164 */ 03165 template<typename _InputIterator, typename _OutputIterator, 03166 typename _Predicate, typename _Tp> 03167 inline _OutputIterator 03168 replace_copy_if(_InputIterator __first, _InputIterator __last, 03169 _OutputIterator __result, 03170 _Predicate __pred, const _Tp& __new_value) 03171 { 03172 // concept requirements 03173 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03174 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 03175 typename iterator_traits<_InputIterator>::value_type>) 03176 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 03177 typename iterator_traits<_InputIterator>::value_type>) 03178 __glibcxx_requires_valid_range(__first, __last); 03179 03180 return std::__replace_copy_if(__first, __last, __result, 03181 __gnu_cxx::__ops::__pred_iter(__pred), 03182 __new_value); 03183 } 03184 03185 template<typename _InputIterator, typename _Predicate> 03186 typename iterator_traits<_InputIterator>::difference_type 03187 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 03188 { 03189 typename iterator_traits<_InputIterator>::difference_type __n = 0; 03190 for (; __first != __last; ++__first) 03191 if (__pred(__first)) 03192 ++__n; 03193 return __n; 03194 } 03195 03196 #if __cplusplus >= 201103L 03197 /** 03198 * @brief Determines whether the elements of a sequence are sorted. 03199 * @ingroup sorting_algorithms 03200 * @param __first An iterator. 03201 * @param __last Another iterator. 03202 * @return True if the elements are sorted, false otherwise. 03203 */ 03204 template<typename _ForwardIterator> 03205 inline bool 03206 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 03207 { return std::is_sorted_until(__first, __last) == __last; } 03208 03209 /** 03210 * @brief Determines whether the elements of a sequence are sorted 03211 * according to a comparison functor. 03212 * @ingroup sorting_algorithms 03213 * @param __first An iterator. 03214 * @param __last Another iterator. 03215 * @param __comp A comparison functor. 03216 * @return True if the elements are sorted, false otherwise. 03217 */ 03218 template<typename _ForwardIterator, typename _Compare> 03219 inline bool 03220 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 03221 _Compare __comp) 03222 { return std::is_sorted_until(__first, __last, __comp) == __last; } 03223 03224 template<typename _ForwardIterator, typename _Compare> 03225 _ForwardIterator 03226 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 03227 _Compare __comp) 03228 { 03229 if (__first == __last) 03230 return __last; 03231 03232 _ForwardIterator __next = __first; 03233 for (++__next; __next != __last; __first = __next, (void)++__next) 03234 if (__comp(__next, __first)) 03235 return __next; 03236 return __next; 03237 } 03238 03239 /** 03240 * @brief Determines the end of a sorted sequence. 03241 * @ingroup sorting_algorithms 03242 * @param __first An iterator. 03243 * @param __last Another iterator. 03244 * @return An iterator pointing to the last iterator i in [__first, __last) 03245 * for which the range [__first, i) is sorted. 03246 */ 03247 template<typename _ForwardIterator> 03248 inline _ForwardIterator 03249 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) 03250 { 03251 // concept requirements 03252 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03253 __glibcxx_function_requires(_LessThanComparableConcept< 03254 typename iterator_traits<_ForwardIterator>::value_type>) 03255 __glibcxx_requires_valid_range(__first, __last); 03256 __glibcxx_requires_irreflexive(__first, __last); 03257 03258 return std::__is_sorted_until(__first, __last, 03259 __gnu_cxx::__ops::__iter_less_iter()); 03260 } 03261 03262 /** 03263 * @brief Determines the end of a sorted sequence using comparison functor. 03264 * @ingroup sorting_algorithms 03265 * @param __first An iterator. 03266 * @param __last Another iterator. 03267 * @param __comp A comparison functor. 03268 * @return An iterator pointing to the last iterator i in [__first, __last) 03269 * for which the range [__first, i) is sorted. 03270 */ 03271 template<typename _ForwardIterator, typename _Compare> 03272 inline _ForwardIterator 03273 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 03274 _Compare __comp) 03275 { 03276 // concept requirements 03277 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03278 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03279 typename iterator_traits<_ForwardIterator>::value_type, 03280 typename iterator_traits<_ForwardIterator>::value_type>) 03281 __glibcxx_requires_valid_range(__first, __last); 03282 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 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 __glibcxx_requires_irreflexive(__first, __last); 03408 03409 return std::__minmax_element(__first, __last, 03410 __gnu_cxx::__ops::__iter_less_iter()); 03411 } 03412 03413 /** 03414 * @brief Return a pair of iterators pointing to the minimum and maximum 03415 * elements in a range. 03416 * @ingroup sorting_algorithms 03417 * @param __first Start of range. 03418 * @param __last End of range. 03419 * @param __comp Comparison functor. 03420 * @return make_pair(m, M), where m is the first iterator i in 03421 * [__first, __last) such that no other element in the range is 03422 * smaller, and where M is the last iterator i in [__first, __last) 03423 * such that no other element in the range is larger. 03424 */ 03425 template<typename _ForwardIterator, typename _Compare> 03426 _GLIBCXX14_CONSTEXPR 03427 inline pair<_ForwardIterator, _ForwardIterator> 03428 minmax_element(_ForwardIterator __first, _ForwardIterator __last, 03429 _Compare __comp) 03430 { 03431 // concept requirements 03432 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03433 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03434 typename iterator_traits<_ForwardIterator>::value_type, 03435 typename iterator_traits<_ForwardIterator>::value_type>) 03436 __glibcxx_requires_valid_range(__first, __last); 03437 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 03438 03439 return std::__minmax_element(__first, __last, 03440 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 03441 } 03442 03443 // N2722 + DR 915. 03444 template<typename _Tp> 03445 _GLIBCXX14_CONSTEXPR 03446 inline _Tp 03447 min(initializer_list<_Tp> __l) 03448 { return *std::min_element(__l.begin(), __l.end()); } 03449 03450 template<typename _Tp, typename _Compare> 03451 _GLIBCXX14_CONSTEXPR 03452 inline _Tp 03453 min(initializer_list<_Tp> __l, _Compare __comp) 03454 { return *std::min_element(__l.begin(), __l.end(), __comp); } 03455 03456 template<typename _Tp> 03457 _GLIBCXX14_CONSTEXPR 03458 inline _Tp 03459 max(initializer_list<_Tp> __l) 03460 { return *std::max_element(__l.begin(), __l.end()); } 03461 03462 template<typename _Tp, typename _Compare> 03463 _GLIBCXX14_CONSTEXPR 03464 inline _Tp 03465 max(initializer_list<_Tp> __l, _Compare __comp) 03466 { return *std::max_element(__l.begin(), __l.end(), __comp); } 03467 03468 template<typename _Tp> 03469 _GLIBCXX14_CONSTEXPR 03470 inline pair<_Tp, _Tp> 03471 minmax(initializer_list<_Tp> __l) 03472 { 03473 pair<const _Tp*, const _Tp*> __p = 03474 std::minmax_element(__l.begin(), __l.end()); 03475 return std::make_pair(*__p.first, *__p.second); 03476 } 03477 03478 template<typename _Tp, typename _Compare> 03479 _GLIBCXX14_CONSTEXPR 03480 inline pair<_Tp, _Tp> 03481 minmax(initializer_list<_Tp> __l, _Compare __comp) 03482 { 03483 pair<const _Tp*, const _Tp*> __p = 03484 std::minmax_element(__l.begin(), __l.end(), __comp); 03485 return std::make_pair(*__p.first, *__p.second); 03486 } 03487 03488 template<typename _ForwardIterator1, typename _ForwardIterator2, 03489 typename _BinaryPredicate> 03490 bool 03491 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03492 _ForwardIterator2 __first2, _BinaryPredicate __pred) 03493 { 03494 // Efficiently compare identical prefixes: O(N) if sequences 03495 // have the same elements in the same order. 03496 for (; __first1 != __last1; ++__first1, (void)++__first2) 03497 if (!__pred(__first1, __first2)) 03498 break; 03499 03500 if (__first1 == __last1) 03501 return true; 03502 03503 // Establish __last2 assuming equal ranges by iterating over the 03504 // rest of the list. 03505 _ForwardIterator2 __last2 = __first2; 03506 std::advance(__last2, std::distance(__first1, __last1)); 03507 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 03508 { 03509 if (__scan != std::__find_if(__first1, __scan, 03510 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 03511 continue; // We've seen this one before. 03512 03513 auto __matches 03514 = std::__count_if(__first2, __last2, 03515 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 03516 if (0 == __matches || 03517 std::__count_if(__scan, __last1, 03518 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 03519 != __matches) 03520 return false; 03521 } 03522 return true; 03523 } 03524 03525 /** 03526 * @brief Checks whether a permutation of the second sequence is equal 03527 * to the first sequence. 03528 * @ingroup non_mutating_algorithms 03529 * @param __first1 Start of first range. 03530 * @param __last1 End of first range. 03531 * @param __first2 Start of second range. 03532 * @return true if there exists a permutation of the elements in the range 03533 * [__first2, __first2 + (__last1 - __first1)), beginning with 03534 * ForwardIterator2 begin, such that equal(__first1, __last1, begin) 03535 * returns true; otherwise, returns false. 03536 */ 03537 template<typename _ForwardIterator1, typename _ForwardIterator2> 03538 inline bool 03539 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03540 _ForwardIterator2 __first2) 03541 { 03542 // concept requirements 03543 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 03544 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 03545 __glibcxx_function_requires(_EqualOpConcept< 03546 typename iterator_traits<_ForwardIterator1>::value_type, 03547 typename iterator_traits<_ForwardIterator2>::value_type>) 03548 __glibcxx_requires_valid_range(__first1, __last1); 03549 03550 return std::__is_permutation(__first1, __last1, __first2, 03551 __gnu_cxx::__ops::__iter_equal_to_iter()); 03552 } 03553 03554 /** 03555 * @brief Checks whether a permutation of the second sequence is equal 03556 * to the first sequence. 03557 * @ingroup non_mutating_algorithms 03558 * @param __first1 Start of first range. 03559 * @param __last1 End of first range. 03560 * @param __first2 Start of second range. 03561 * @param __pred A binary predicate. 03562 * @return true if there exists a permutation of the elements in 03563 * the range [__first2, __first2 + (__last1 - __first1)), 03564 * beginning with ForwardIterator2 begin, such that 03565 * equal(__first1, __last1, __begin, __pred) returns true; 03566 * otherwise, returns false. 03567 */ 03568 template<typename _ForwardIterator1, typename _ForwardIterator2, 03569 typename _BinaryPredicate> 03570 inline bool 03571 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03572 _ForwardIterator2 __first2, _BinaryPredicate __pred) 03573 { 03574 // concept requirements 03575 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 03576 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 03577 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 03578 typename iterator_traits<_ForwardIterator1>::value_type, 03579 typename iterator_traits<_ForwardIterator2>::value_type>) 03580 __glibcxx_requires_valid_range(__first1, __last1); 03581 03582 return std::__is_permutation(__first1, __last1, __first2, 03583 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 03584 } 03585 03586 #if __cplusplus > 201103L 03587 template<typename _ForwardIterator1, typename _ForwardIterator2, 03588 typename _BinaryPredicate> 03589 bool 03590 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03591 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 03592 _BinaryPredicate __pred) 03593 { 03594 using _Cat1 03595 = typename iterator_traits<_ForwardIterator1>::iterator_category; 03596 using _Cat2 03597 = typename iterator_traits<_ForwardIterator2>::iterator_category; 03598 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>; 03599 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>; 03600 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA(); 03601 if (__ra_iters) 03602 { 03603 auto __d1 = std::distance(__first1, __last1); 03604 auto __d2 = std::distance(__first2, __last2); 03605 if (__d1 != __d2) 03606 return false; 03607 } 03608 03609 // Efficiently compare identical prefixes: O(N) if sequences 03610 // have the same elements in the same order. 03611 for (; __first1 != __last1 && __first2 != __last2; 03612 ++__first1, (void)++__first2) 03613 if (!__pred(__first1, __first2)) 03614 break; 03615 03616 if (__ra_iters) 03617 { 03618 if (__first1 == __last1) 03619 return true; 03620 } 03621 else 03622 { 03623 auto __d1 = std::distance(__first1, __last1); 03624 auto __d2 = std::distance(__first2, __last2); 03625 if (__d1 == 0 && __d2 == 0) 03626 return true; 03627 if (__d1 != __d2) 03628 return false; 03629 } 03630 03631 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 03632 { 03633 if (__scan != std::__find_if(__first1, __scan, 03634 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 03635 continue; // We've seen this one before. 03636 03637 auto __matches = std::__count_if(__first2, __last2, 03638 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 03639 if (0 == __matches 03640 || std::__count_if(__scan, __last1, 03641 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 03642 != __matches) 03643 return false; 03644 } 03645 return true; 03646 } 03647 03648 /** 03649 * @brief Checks whether a permutaion of the second sequence is equal 03650 * to the first sequence. 03651 * @ingroup non_mutating_algorithms 03652 * @param __first1 Start of first range. 03653 * @param __last1 End of first range. 03654 * @param __first2 Start of second range. 03655 * @param __last2 End of first range. 03656 * @return true if there exists a permutation of the elements in the range 03657 * [__first2, __last2), beginning with ForwardIterator2 begin, 03658 * such that equal(__first1, __last1, begin) returns true; 03659 * otherwise, returns false. 03660 */ 03661 template<typename _ForwardIterator1, typename _ForwardIterator2> 03662 inline bool 03663 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03664 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 03665 { 03666 __glibcxx_requires_valid_range(__first1, __last1); 03667 __glibcxx_requires_valid_range(__first2, __last2); 03668 03669 return 03670 std::__is_permutation(__first1, __last1, __first2, __last2, 03671 __gnu_cxx::__ops::__iter_equal_to_iter()); 03672 } 03673 03674 /** 03675 * @brief Checks whether a permutation of the second sequence is equal 03676 * to the first sequence. 03677 * @ingroup non_mutating_algorithms 03678 * @param __first1 Start of first range. 03679 * @param __last1 End of first range. 03680 * @param __first2 Start of second range. 03681 * @param __last2 End of first range. 03682 * @param __pred A binary predicate. 03683 * @return true if there exists a permutation of the elements in the range 03684 * [__first2, __last2), beginning with ForwardIterator2 begin, 03685 * such that equal(__first1, __last1, __begin, __pred) returns true; 03686 * otherwise, returns false. 03687 */ 03688 template<typename _ForwardIterator1, typename _ForwardIterator2, 03689 typename _BinaryPredicate> 03690 inline bool 03691 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03692 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 03693 _BinaryPredicate __pred) 03694 { 03695 __glibcxx_requires_valid_range(__first1, __last1); 03696 __glibcxx_requires_valid_range(__first2, __last2); 03697 03698 return std::__is_permutation(__first1, __last1, __first2, __last2, 03699 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 03700 } 03701 #endif 03702 03703 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 03704 /** 03705 * @brief Shuffle the elements of a sequence using a uniform random 03706 * number generator. 03707 * @ingroup mutating_algorithms 03708 * @param __first A forward iterator. 03709 * @param __last A forward iterator. 03710 * @param __g A UniformRandomNumberGenerator (26.5.1.3). 03711 * @return Nothing. 03712 * 03713 * Reorders the elements in the range @p [__first,__last) using @p __g to 03714 * provide random numbers. 03715 */ 03716 template<typename _RandomAccessIterator, 03717 typename _UniformRandomNumberGenerator> 03718 void 03719 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 03720 _UniformRandomNumberGenerator&& __g) 03721 { 03722 // concept requirements 03723 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 03724 _RandomAccessIterator>) 03725 __glibcxx_requires_valid_range(__first, __last); 03726 03727 if (__first == __last) 03728 return; 03729 03730 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 03731 _DistanceType; 03732 03733 typedef typename std::make_unsigned<_DistanceType>::type __ud_type; 03734 typedef typename std::uniform_int_distribution<__ud_type> __distr_type; 03735 typedef typename __distr_type::param_type __p_type; 03736 __distr_type __d; 03737 03738 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 03739 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first))); 03740 } 03741 #endif 03742 03743 #endif // C++11 03744 03745 _GLIBCXX_END_NAMESPACE_VERSION 03746 03747 _GLIBCXX_BEGIN_NAMESPACE_ALGO 03748 03749 /** 03750 * @brief Apply a function to every element of a sequence. 03751 * @ingroup non_mutating_algorithms 03752 * @param __first An input iterator. 03753 * @param __last An input iterator. 03754 * @param __f A unary function object. 03755 * @return @p __f (std::move(@p __f) in C++0x). 03756 * 03757 * Applies the function object @p __f to each element in the range 03758 * @p [first,last). @p __f must not modify the order of the sequence. 03759 * If @p __f has a return value it is ignored. 03760 */ 03761 template<typename _InputIterator, typename _Function> 03762 _Function 03763 for_each(_InputIterator __first, _InputIterator __last, _Function __f) 03764 { 03765 // concept requirements 03766 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03767 __glibcxx_requires_valid_range(__first, __last); 03768 for (; __first != __last; ++__first) 03769 __f(*__first); 03770 return _GLIBCXX_MOVE(__f); 03771 } 03772 03773 /** 03774 * @brief Find the first occurrence of a value in a sequence. 03775 * @ingroup non_mutating_algorithms 03776 * @param __first An input iterator. 03777 * @param __last An input iterator. 03778 * @param __val The value to find. 03779 * @return The first iterator @c i in the range @p [__first,__last) 03780 * such that @c *i == @p __val, or @p __last if no such iterator exists. 03781 */ 03782 template<typename _InputIterator, typename _Tp> 03783 inline _InputIterator 03784 find(_InputIterator __first, _InputIterator __last, 03785 const _Tp& __val) 03786 { 03787 // concept requirements 03788 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03789 __glibcxx_function_requires(_EqualOpConcept< 03790 typename iterator_traits<_InputIterator>::value_type, _Tp>) 03791 __glibcxx_requires_valid_range(__first, __last); 03792 return std::__find_if(__first, __last, 03793 __gnu_cxx::__ops::__iter_equals_val(__val)); 03794 } 03795 03796 /** 03797 * @brief Find the first element in a sequence for which a 03798 * predicate is true. 03799 * @ingroup non_mutating_algorithms 03800 * @param __first An input iterator. 03801 * @param __last An input iterator. 03802 * @param __pred A predicate. 03803 * @return The first iterator @c i in the range @p [__first,__last) 03804 * such that @p __pred(*i) is true, or @p __last if no such iterator exists. 03805 */ 03806 template<typename _InputIterator, typename _Predicate> 03807 inline _InputIterator 03808 find_if(_InputIterator __first, _InputIterator __last, 03809 _Predicate __pred) 03810 { 03811 // concept requirements 03812 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03813 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 03814 typename iterator_traits<_InputIterator>::value_type>) 03815 __glibcxx_requires_valid_range(__first, __last); 03816 03817 return std::__find_if(__first, __last, 03818 __gnu_cxx::__ops::__pred_iter(__pred)); 03819 } 03820 03821 /** 03822 * @brief Find element from a set in a sequence. 03823 * @ingroup non_mutating_algorithms 03824 * @param __first1 Start of range to search. 03825 * @param __last1 End of range to search. 03826 * @param __first2 Start of match candidates. 03827 * @param __last2 End of match candidates. 03828 * @return The first iterator @c i in the range 03829 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an 03830 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists. 03831 * 03832 * Searches the range @p [__first1,__last1) for an element that is 03833 * equal to some element in the range [__first2,__last2). If 03834 * found, returns an iterator in the range [__first1,__last1), 03835 * otherwise returns @p __last1. 03836 */ 03837 template<typename _InputIterator, typename _ForwardIterator> 03838 _InputIterator 03839 find_first_of(_InputIterator __first1, _InputIterator __last1, 03840 _ForwardIterator __first2, _ForwardIterator __last2) 03841 { 03842 // concept requirements 03843 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03844 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03845 __glibcxx_function_requires(_EqualOpConcept< 03846 typename iterator_traits<_InputIterator>::value_type, 03847 typename iterator_traits<_ForwardIterator>::value_type>) 03848 __glibcxx_requires_valid_range(__first1, __last1); 03849 __glibcxx_requires_valid_range(__first2, __last2); 03850 03851 for (; __first1 != __last1; ++__first1) 03852 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 03853 if (*__first1 == *__iter) 03854 return __first1; 03855 return __last1; 03856 } 03857 03858 /** 03859 * @brief Find element from a set in a sequence using a predicate. 03860 * @ingroup non_mutating_algorithms 03861 * @param __first1 Start of range to search. 03862 * @param __last1 End of range to search. 03863 * @param __first2 Start of match candidates. 03864 * @param __last2 End of match candidates. 03865 * @param __comp Predicate to use. 03866 * @return The first iterator @c i in the range 03867 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true 03868 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no 03869 * such iterator exists. 03870 * 03871 03872 * Searches the range @p [__first1,__last1) for an element that is 03873 * equal to some element in the range [__first2,__last2). If 03874 * found, returns an iterator in the range [__first1,__last1), 03875 * otherwise returns @p __last1. 03876 */ 03877 template<typename _InputIterator, typename _ForwardIterator, 03878 typename _BinaryPredicate> 03879 _InputIterator 03880 find_first_of(_InputIterator __first1, _InputIterator __last1, 03881 _ForwardIterator __first2, _ForwardIterator __last2, 03882 _BinaryPredicate __comp) 03883 { 03884 // concept requirements 03885 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03886 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03887 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 03888 typename iterator_traits<_InputIterator>::value_type, 03889 typename iterator_traits<_ForwardIterator>::value_type>) 03890 __glibcxx_requires_valid_range(__first1, __last1); 03891 __glibcxx_requires_valid_range(__first2, __last2); 03892 03893 for (; __first1 != __last1; ++__first1) 03894 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 03895 if (__comp(*__first1, *__iter)) 03896 return __first1; 03897 return __last1; 03898 } 03899 03900 /** 03901 * @brief Find two adjacent values in a sequence that are equal. 03902 * @ingroup non_mutating_algorithms 03903 * @param __first A forward iterator. 03904 * @param __last A forward iterator. 03905 * @return The first iterator @c i such that @c i and @c i+1 are both 03906 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1), 03907 * or @p __last if no such iterator exists. 03908 */ 03909 template<typename _ForwardIterator> 03910 inline _ForwardIterator 03911 adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 03912 { 03913 // concept requirements 03914 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03915 __glibcxx_function_requires(_EqualityComparableConcept< 03916 typename iterator_traits<_ForwardIterator>::value_type>) 03917 __glibcxx_requires_valid_range(__first, __last); 03918 03919 return std::__adjacent_find(__first, __last, 03920 __gnu_cxx::__ops::__iter_equal_to_iter()); 03921 } 03922 03923 /** 03924 * @brief Find two adjacent values in a sequence using a predicate. 03925 * @ingroup non_mutating_algorithms 03926 * @param __first A forward iterator. 03927 * @param __last A forward iterator. 03928 * @param __binary_pred A binary predicate. 03929 * @return The first iterator @c i such that @c i and @c i+1 are both 03930 * valid iterators in @p [__first,__last) and such that 03931 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator 03932 * exists. 03933 */ 03934 template<typename _ForwardIterator, typename _BinaryPredicate> 03935 inline _ForwardIterator 03936 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 03937 _BinaryPredicate __binary_pred) 03938 { 03939 // concept requirements 03940 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03941 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 03942 typename iterator_traits<_ForwardIterator>::value_type, 03943 typename iterator_traits<_ForwardIterator>::value_type>) 03944 __glibcxx_requires_valid_range(__first, __last); 03945 03946 return std::__adjacent_find(__first, __last, 03947 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 03948 } 03949 03950 /** 03951 * @brief Count the number of copies of a value in a sequence. 03952 * @ingroup non_mutating_algorithms 03953 * @param __first An input iterator. 03954 * @param __last An input iterator. 03955 * @param __value The value to be counted. 03956 * @return The number of iterators @c i in the range @p [__first,__last) 03957 * for which @c *i == @p __value 03958 */ 03959 template<typename _InputIterator, typename _Tp> 03960 inline typename iterator_traits<_InputIterator>::difference_type 03961 count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 03962 { 03963 // concept requirements 03964 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03965 __glibcxx_function_requires(_EqualOpConcept< 03966 typename iterator_traits<_InputIterator>::value_type, _Tp>) 03967 __glibcxx_requires_valid_range(__first, __last); 03968 03969 return std::__count_if(__first, __last, 03970 __gnu_cxx::__ops::__iter_equals_val(__value)); 03971 } 03972 03973 /** 03974 * @brief Count the elements of a sequence for which a predicate is true. 03975 * @ingroup non_mutating_algorithms 03976 * @param __first An input iterator. 03977 * @param __last An input iterator. 03978 * @param __pred A predicate. 03979 * @return The number of iterators @c i in the range @p [__first,__last) 03980 * for which @p __pred(*i) is true. 03981 */ 03982 template<typename _InputIterator, typename _Predicate> 03983 inline typename iterator_traits<_InputIterator>::difference_type 03984 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 03985 { 03986 // concept requirements 03987 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03988 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 03989 typename iterator_traits<_InputIterator>::value_type>) 03990 __glibcxx_requires_valid_range(__first, __last); 03991 03992 return std::__count_if(__first, __last, 03993 __gnu_cxx::__ops::__pred_iter(__pred)); 03994 } 03995 03996 /** 03997 * @brief Search a sequence for a matching sub-sequence. 03998 * @ingroup non_mutating_algorithms 03999 * @param __first1 A forward iterator. 04000 * @param __last1 A forward iterator. 04001 * @param __first2 A forward iterator. 04002 * @param __last2 A forward iterator. 04003 * @return The first iterator @c i in the range @p 04004 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p 04005 * *(__first2+N) for each @c N in the range @p 04006 * [0,__last2-__first2), or @p __last1 if no such iterator exists. 04007 * 04008 * Searches the range @p [__first1,__last1) for a sub-sequence that 04009 * compares equal value-by-value with the sequence given by @p 04010 * [__first2,__last2) and returns an iterator to the first element 04011 * of the sub-sequence, or @p __last1 if the sub-sequence is not 04012 * found. 04013 * 04014 * Because the sub-sequence must lie completely within the range @p 04015 * [__first1,__last1) it must start at a position less than @p 04016 * __last1-(__last2-__first2) where @p __last2-__first2 is the 04017 * length of the sub-sequence. 04018 * 04019 * This means that the returned iterator @c i will be in the range 04020 * @p [__first1,__last1-(__last2-__first2)) 04021 */ 04022 template<typename _ForwardIterator1, typename _ForwardIterator2> 04023 inline _ForwardIterator1 04024 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04025 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 04026 { 04027 // concept requirements 04028 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 04029 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 04030 __glibcxx_function_requires(_EqualOpConcept< 04031 typename iterator_traits<_ForwardIterator1>::value_type, 04032 typename iterator_traits<_ForwardIterator2>::value_type>) 04033 __glibcxx_requires_valid_range(__first1, __last1); 04034 __glibcxx_requires_valid_range(__first2, __last2); 04035 04036 return std::__search(__first1, __last1, __first2, __last2, 04037 __gnu_cxx::__ops::__iter_equal_to_iter()); 04038 } 04039 04040 /** 04041 * @brief Search a sequence for a matching sub-sequence using a predicate. 04042 * @ingroup non_mutating_algorithms 04043 * @param __first1 A forward iterator. 04044 * @param __last1 A forward iterator. 04045 * @param __first2 A forward iterator. 04046 * @param __last2 A forward iterator. 04047 * @param __predicate A binary predicate. 04048 * @return The first iterator @c i in the range 04049 * @p [__first1,__last1-(__last2-__first2)) such that 04050 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range 04051 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists. 04052 * 04053 * Searches the range @p [__first1,__last1) for a sub-sequence that 04054 * compares equal value-by-value with the sequence given by @p 04055 * [__first2,__last2), using @p __predicate to determine equality, 04056 * and returns an iterator to the first element of the 04057 * sub-sequence, or @p __last1 if no such iterator exists. 04058 * 04059 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 04060 */ 04061 template<typename _ForwardIterator1, typename _ForwardIterator2, 04062 typename _BinaryPredicate> 04063 inline _ForwardIterator1 04064 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04065 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 04066 _BinaryPredicate __predicate) 04067 { 04068 // concept requirements 04069 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 04070 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 04071 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04072 typename iterator_traits<_ForwardIterator1>::value_type, 04073 typename iterator_traits<_ForwardIterator2>::value_type>) 04074 __glibcxx_requires_valid_range(__first1, __last1); 04075 __glibcxx_requires_valid_range(__first2, __last2); 04076 04077 return std::__search(__first1, __last1, __first2, __last2, 04078 __gnu_cxx::__ops::__iter_comp_iter(__predicate)); 04079 } 04080 04081 /** 04082 * @brief Search a sequence for a number of consecutive values. 04083 * @ingroup non_mutating_algorithms 04084 * @param __first A forward iterator. 04085 * @param __last A forward iterator. 04086 * @param __count The number of consecutive values. 04087 * @param __val The value to find. 04088 * @return The first iterator @c i in the range @p 04089 * [__first,__last-__count) such that @c *(i+N) == @p __val for 04090 * each @c N in the range @p [0,__count), or @p __last if no such 04091 * iterator exists. 04092 * 04093 * Searches the range @p [__first,__last) for @p count consecutive elements 04094 * equal to @p __val. 04095 */ 04096 template<typename _ForwardIterator, typename _Integer, typename _Tp> 04097 inline _ForwardIterator 04098 search_n(_ForwardIterator __first, _ForwardIterator __last, 04099 _Integer __count, const _Tp& __val) 04100 { 04101 // concept requirements 04102 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04103 __glibcxx_function_requires(_EqualOpConcept< 04104 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04105 __glibcxx_requires_valid_range(__first, __last); 04106 04107 return std::__search_n(__first, __last, __count, 04108 __gnu_cxx::__ops::__iter_equals_val(__val)); 04109 } 04110 04111 04112 /** 04113 * @brief Search a sequence for a number of consecutive values using a 04114 * predicate. 04115 * @ingroup non_mutating_algorithms 04116 * @param __first A forward iterator. 04117 * @param __last A forward iterator. 04118 * @param __count The number of consecutive values. 04119 * @param __val The value to find. 04120 * @param __binary_pred A binary predicate. 04121 * @return The first iterator @c i in the range @p 04122 * [__first,__last-__count) such that @p 04123 * __binary_pred(*(i+N),__val) is true for each @c N in the range 04124 * @p [0,__count), or @p __last if no such iterator exists. 04125 * 04126 * Searches the range @p [__first,__last) for @p __count 04127 * consecutive elements for which the predicate returns true. 04128 */ 04129 template<typename _ForwardIterator, typename _Integer, typename _Tp, 04130 typename _BinaryPredicate> 04131 inline _ForwardIterator 04132 search_n(_ForwardIterator __first, _ForwardIterator __last, 04133 _Integer __count, const _Tp& __val, 04134 _BinaryPredicate __binary_pred) 04135 { 04136 // concept requirements 04137 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04138 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04139 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04140 __glibcxx_requires_valid_range(__first, __last); 04141 04142 return std::__search_n(__first, __last, __count, 04143 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val)); 04144 } 04145 04146 04147 /** 04148 * @brief Perform an operation on a sequence. 04149 * @ingroup mutating_algorithms 04150 * @param __first An input iterator. 04151 * @param __last An input iterator. 04152 * @param __result An output iterator. 04153 * @param __unary_op A unary operator. 04154 * @return An output iterator equal to @p __result+(__last-__first). 04155 * 04156 * Applies the operator to each element in the input range and assigns 04157 * the results to successive elements of the output sequence. 04158 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the 04159 * range @p [0,__last-__first). 04160 * 04161 * @p unary_op must not alter its argument. 04162 */ 04163 template<typename _InputIterator, typename _OutputIterator, 04164 typename _UnaryOperation> 04165 _OutputIterator 04166 transform(_InputIterator __first, _InputIterator __last, 04167 _OutputIterator __result, _UnaryOperation __unary_op) 04168 { 04169 // concept requirements 04170 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04171 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04172 // "the type returned by a _UnaryOperation" 04173 __typeof__(__unary_op(*__first))>) 04174 __glibcxx_requires_valid_range(__first, __last); 04175 04176 for (; __first != __last; ++__first, (void)++__result) 04177 *__result = __unary_op(*__first); 04178 return __result; 04179 } 04180 04181 /** 04182 * @brief Perform an operation on corresponding elements of two sequences. 04183 * @ingroup mutating_algorithms 04184 * @param __first1 An input iterator. 04185 * @param __last1 An input iterator. 04186 * @param __first2 An input iterator. 04187 * @param __result An output iterator. 04188 * @param __binary_op A binary operator. 04189 * @return An output iterator equal to @p result+(last-first). 04190 * 04191 * Applies the operator to the corresponding elements in the two 04192 * input ranges and assigns the results to successive elements of the 04193 * output sequence. 04194 * Evaluates @p 04195 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each 04196 * @c N in the range @p [0,__last1-__first1). 04197 * 04198 * @p binary_op must not alter either of its arguments. 04199 */ 04200 template<typename _InputIterator1, typename _InputIterator2, 04201 typename _OutputIterator, typename _BinaryOperation> 04202 _OutputIterator 04203 transform(_InputIterator1 __first1, _InputIterator1 __last1, 04204 _InputIterator2 __first2, _OutputIterator __result, 04205 _BinaryOperation __binary_op) 04206 { 04207 // concept requirements 04208 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04209 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04210 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04211 // "the type returned by a _BinaryOperation" 04212 __typeof__(__binary_op(*__first1,*__first2))>) 04213 __glibcxx_requires_valid_range(__first1, __last1); 04214 04215 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result) 04216 *__result = __binary_op(*__first1, *__first2); 04217 return __result; 04218 } 04219 04220 /** 04221 * @brief Replace each occurrence of one value in a sequence with another 04222 * value. 04223 * @ingroup mutating_algorithms 04224 * @param __first A forward iterator. 04225 * @param __last A forward iterator. 04226 * @param __old_value The value to be replaced. 04227 * @param __new_value The replacement value. 04228 * @return replace() returns no value. 04229 * 04230 * For each iterator @c i in the range @p [__first,__last) if @c *i == 04231 * @p __old_value then the assignment @c *i = @p __new_value is performed. 04232 */ 04233 template<typename _ForwardIterator, typename _Tp> 04234 void 04235 replace(_ForwardIterator __first, _ForwardIterator __last, 04236 const _Tp& __old_value, const _Tp& __new_value) 04237 { 04238 // concept requirements 04239 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04240 _ForwardIterator>) 04241 __glibcxx_function_requires(_EqualOpConcept< 04242 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04243 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 04244 typename iterator_traits<_ForwardIterator>::value_type>) 04245 __glibcxx_requires_valid_range(__first, __last); 04246 04247 for (; __first != __last; ++__first) 04248 if (*__first == __old_value) 04249 *__first = __new_value; 04250 } 04251 04252 /** 04253 * @brief Replace each value in a sequence for which a predicate returns 04254 * true with another value. 04255 * @ingroup mutating_algorithms 04256 * @param __first A forward iterator. 04257 * @param __last A forward iterator. 04258 * @param __pred A predicate. 04259 * @param __new_value The replacement value. 04260 * @return replace_if() returns no value. 04261 * 04262 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i) 04263 * is true then the assignment @c *i = @p __new_value is performed. 04264 */ 04265 template<typename _ForwardIterator, typename _Predicate, typename _Tp> 04266 void 04267 replace_if(_ForwardIterator __first, _ForwardIterator __last, 04268 _Predicate __pred, const _Tp& __new_value) 04269 { 04270 // concept requirements 04271 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04272 _ForwardIterator>) 04273 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 04274 typename iterator_traits<_ForwardIterator>::value_type>) 04275 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 04276 typename iterator_traits<_ForwardIterator>::value_type>) 04277 __glibcxx_requires_valid_range(__first, __last); 04278 04279 for (; __first != __last; ++__first) 04280 if (__pred(*__first)) 04281 *__first = __new_value; 04282 } 04283 04284 /** 04285 * @brief Assign the result of a function object to each value in a 04286 * sequence. 04287 * @ingroup mutating_algorithms 04288 * @param __first A forward iterator. 04289 * @param __last A forward iterator. 04290 * @param __gen A function object taking no arguments and returning 04291 * std::iterator_traits<_ForwardIterator>::value_type 04292 * @return generate() returns no value. 04293 * 04294 * Performs the assignment @c *i = @p __gen() for each @c i in the range 04295 * @p [__first,__last). 04296 */ 04297 template<typename _ForwardIterator, typename _Generator> 04298 void 04299 generate(_ForwardIterator __first, _ForwardIterator __last, 04300 _Generator __gen) 04301 { 04302 // concept requirements 04303 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04304 __glibcxx_function_requires(_GeneratorConcept<_Generator, 04305 typename iterator_traits<_ForwardIterator>::value_type>) 04306 __glibcxx_requires_valid_range(__first, __last); 04307 04308 for (; __first != __last; ++__first) 04309 *__first = __gen(); 04310 } 04311 04312 /** 04313 * @brief Assign the result of a function object to each value in a 04314 * sequence. 04315 * @ingroup mutating_algorithms 04316 * @param __first A forward iterator. 04317 * @param __n The length of the sequence. 04318 * @param __gen A function object taking no arguments and returning 04319 * std::iterator_traits<_ForwardIterator>::value_type 04320 * @return The end of the sequence, @p __first+__n 04321 * 04322 * Performs the assignment @c *i = @p __gen() for each @c i in the range 04323 * @p [__first,__first+__n). 04324 * 04325 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04326 * DR 865. More algorithms that throw away information 04327 */ 04328 template<typename _OutputIterator, typename _Size, typename _Generator> 04329 _OutputIterator 04330 generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 04331 { 04332 // concept requirements 04333 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04334 // "the type returned by a _Generator" 04335 __typeof__(__gen())>) 04336 04337 for (__decltype(__n + 0) __niter = __n; 04338 __niter > 0; --__niter, ++__first) 04339 *__first = __gen(); 04340 return __first; 04341 } 04342 04343 /** 04344 * @brief Copy a sequence, removing consecutive duplicate values. 04345 * @ingroup mutating_algorithms 04346 * @param __first An input iterator. 04347 * @param __last An input iterator. 04348 * @param __result An output iterator. 04349 * @return An iterator designating the end of the resulting sequence. 04350 * 04351 * Copies each element in the range @p [__first,__last) to the range 04352 * beginning at @p __result, except that only the first element is copied 04353 * from groups of consecutive elements that compare equal. 04354 * unique_copy() is stable, so the relative order of elements that are 04355 * copied is unchanged. 04356 * 04357 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04358 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 04359 * 04360 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04361 * DR 538. 241 again: Does unique_copy() require CopyConstructible and 04362 * Assignable? 04363 */ 04364 template<typename _InputIterator, typename _OutputIterator> 04365 inline _OutputIterator 04366 unique_copy(_InputIterator __first, _InputIterator __last, 04367 _OutputIterator __result) 04368 { 04369 // concept requirements 04370 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04371 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04372 typename iterator_traits<_InputIterator>::value_type>) 04373 __glibcxx_function_requires(_EqualityComparableConcept< 04374 typename iterator_traits<_InputIterator>::value_type>) 04375 __glibcxx_requires_valid_range(__first, __last); 04376 04377 if (__first == __last) 04378 return __result; 04379 return std::__unique_copy(__first, __last, __result, 04380 __gnu_cxx::__ops::__iter_equal_to_iter(), 04381 std::__iterator_category(__first), 04382 std::__iterator_category(__result)); 04383 } 04384 04385 /** 04386 * @brief Copy a sequence, removing consecutive values using a predicate. 04387 * @ingroup mutating_algorithms 04388 * @param __first An input iterator. 04389 * @param __last An input iterator. 04390 * @param __result An output iterator. 04391 * @param __binary_pred A binary predicate. 04392 * @return An iterator designating the end of the resulting sequence. 04393 * 04394 * Copies each element in the range @p [__first,__last) to the range 04395 * beginning at @p __result, except that only the first element is copied 04396 * from groups of consecutive elements for which @p __binary_pred returns 04397 * true. 04398 * unique_copy() is stable, so the relative order of elements that are 04399 * copied is unchanged. 04400 * 04401 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04402 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 04403 */ 04404 template<typename _InputIterator, typename _OutputIterator, 04405 typename _BinaryPredicate> 04406 inline _OutputIterator 04407 unique_copy(_InputIterator __first, _InputIterator __last, 04408 _OutputIterator __result, 04409 _BinaryPredicate __binary_pred) 04410 { 04411 // concept requirements -- predicates checked later 04412 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04413 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04414 typename iterator_traits<_InputIterator>::value_type>) 04415 __glibcxx_requires_valid_range(__first, __last); 04416 04417 if (__first == __last) 04418 return __result; 04419 return std::__unique_copy(__first, __last, __result, 04420 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred), 04421 std::__iterator_category(__first), 04422 std::__iterator_category(__result)); 04423 } 04424 04425 #if _GLIBCXX_HOSTED 04426 /** 04427 * @brief Randomly shuffle the elements of a sequence. 04428 * @ingroup mutating_algorithms 04429 * @param __first A forward iterator. 04430 * @param __last A forward iterator. 04431 * @return Nothing. 04432 * 04433 * Reorder the elements in the range @p [__first,__last) using a random 04434 * distribution, so that every possible ordering of the sequence is 04435 * equally likely. 04436 */ 04437 template<typename _RandomAccessIterator> 04438 inline void 04439 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 04440 { 04441 // concept requirements 04442 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04443 _RandomAccessIterator>) 04444 __glibcxx_requires_valid_range(__first, __last); 04445 04446 if (__first != __last) 04447 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 04448 { 04449 // XXX rand() % N is not uniformly distributed 04450 _RandomAccessIterator __j = __first 04451 + std::rand() % ((__i - __first) + 1); 04452 if (__i != __j) 04453 std::iter_swap(__i, __j); 04454 } 04455 } 04456 #endif 04457 04458 /** 04459 * @brief Shuffle the elements of a sequence using a random number 04460 * generator. 04461 * @ingroup mutating_algorithms 04462 * @param __first A forward iterator. 04463 * @param __last A forward iterator. 04464 * @param __rand The RNG functor or function. 04465 * @return Nothing. 04466 * 04467 * Reorders the elements in the range @p [__first,__last) using @p __rand to 04468 * provide a random distribution. Calling @p __rand(N) for a positive 04469 * integer @p N should return a randomly chosen integer from the 04470 * range [0,N). 04471 */ 04472 template<typename _RandomAccessIterator, typename _RandomNumberGenerator> 04473 void 04474 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 04475 #if __cplusplus >= 201103L 04476 _RandomNumberGenerator&& __rand) 04477 #else 04478 _RandomNumberGenerator& __rand) 04479 #endif 04480 { 04481 // concept requirements 04482 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04483 _RandomAccessIterator>) 04484 __glibcxx_requires_valid_range(__first, __last); 04485 04486 if (__first == __last) 04487 return; 04488 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 04489 { 04490 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1); 04491 if (__i != __j) 04492 std::iter_swap(__i, __j); 04493 } 04494 } 04495 04496 04497 /** 04498 * @brief Move elements for which a predicate is true to the beginning 04499 * of a sequence. 04500 * @ingroup mutating_algorithms 04501 * @param __first A forward iterator. 04502 * @param __last A forward iterator. 04503 * @param __pred A predicate functor. 04504 * @return An iterator @p middle such that @p __pred(i) is true for each 04505 * iterator @p i in the range @p [__first,middle) and false for each @p i 04506 * in the range @p [middle,__last). 04507 * 04508 * @p __pred must not modify its operand. @p partition() does not preserve 04509 * the relative ordering of elements in each group, use 04510 * @p stable_partition() if this is needed. 04511 */ 04512 template<typename _ForwardIterator, typename _Predicate> 04513 inline _ForwardIterator 04514 partition(_ForwardIterator __first, _ForwardIterator __last, 04515 _Predicate __pred) 04516 { 04517 // concept requirements 04518 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04519 _ForwardIterator>) 04520 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 04521 typename iterator_traits<_ForwardIterator>::value_type>) 04522 __glibcxx_requires_valid_range(__first, __last); 04523 04524 return std::__partition(__first, __last, __pred, 04525 std::__iterator_category(__first)); 04526 } 04527 04528 04529 /** 04530 * @brief Sort the smallest elements of a sequence. 04531 * @ingroup sorting_algorithms 04532 * @param __first An iterator. 04533 * @param __middle Another iterator. 04534 * @param __last Another iterator. 04535 * @return Nothing. 04536 * 04537 * Sorts the smallest @p (__middle-__first) elements in the range 04538 * @p [first,last) and moves them to the range @p [__first,__middle). The 04539 * order of the remaining elements in the range @p [__middle,__last) is 04540 * undefined. 04541 * After the sort if @e i and @e j are iterators in the range 04542 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 04543 * the range @p [__middle,__last) then *j<*i and *k<*i are both false. 04544 */ 04545 template<typename _RandomAccessIterator> 04546 inline void 04547 partial_sort(_RandomAccessIterator __first, 04548 _RandomAccessIterator __middle, 04549 _RandomAccessIterator __last) 04550 { 04551 // concept requirements 04552 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04553 _RandomAccessIterator>) 04554 __glibcxx_function_requires(_LessThanComparableConcept< 04555 typename iterator_traits<_RandomAccessIterator>::value_type>) 04556 __glibcxx_requires_valid_range(__first, __middle); 04557 __glibcxx_requires_valid_range(__middle, __last); 04558 __glibcxx_requires_irreflexive(__first, __last); 04559 04560 std::__partial_sort(__first, __middle, __last, 04561 __gnu_cxx::__ops::__iter_less_iter()); 04562 } 04563 04564 /** 04565 * @brief Sort the smallest elements of a sequence using a predicate 04566 * for comparison. 04567 * @ingroup sorting_algorithms 04568 * @param __first An iterator. 04569 * @param __middle Another iterator. 04570 * @param __last Another iterator. 04571 * @param __comp A comparison functor. 04572 * @return Nothing. 04573 * 04574 * Sorts the smallest @p (__middle-__first) elements in the range 04575 * @p [__first,__last) and moves them to the range @p [__first,__middle). The 04576 * order of the remaining elements in the range @p [__middle,__last) is 04577 * undefined. 04578 * After the sort if @e i and @e j are iterators in the range 04579 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 04580 * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i) 04581 * are both false. 04582 */ 04583 template<typename _RandomAccessIterator, typename _Compare> 04584 inline void 04585 partial_sort(_RandomAccessIterator __first, 04586 _RandomAccessIterator __middle, 04587 _RandomAccessIterator __last, 04588 _Compare __comp) 04589 { 04590 // concept requirements 04591 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04592 _RandomAccessIterator>) 04593 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04594 typename iterator_traits<_RandomAccessIterator>::value_type, 04595 typename iterator_traits<_RandomAccessIterator>::value_type>) 04596 __glibcxx_requires_valid_range(__first, __middle); 04597 __glibcxx_requires_valid_range(__middle, __last); 04598 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 04599 04600 std::__partial_sort(__first, __middle, __last, 04601 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04602 } 04603 04604 /** 04605 * @brief Sort a sequence just enough to find a particular position. 04606 * @ingroup sorting_algorithms 04607 * @param __first An iterator. 04608 * @param __nth Another iterator. 04609 * @param __last Another iterator. 04610 * @return Nothing. 04611 * 04612 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 04613 * is the same element that would have been in that position had the 04614 * whole sequence been sorted. The elements either side of @p *__nth are 04615 * not completely sorted, but for any iterator @e i in the range 04616 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 04617 * holds that *j < *i is false. 04618 */ 04619 template<typename _RandomAccessIterator> 04620 inline void 04621 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 04622 _RandomAccessIterator __last) 04623 { 04624 // concept requirements 04625 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04626 _RandomAccessIterator>) 04627 __glibcxx_function_requires(_LessThanComparableConcept< 04628 typename iterator_traits<_RandomAccessIterator>::value_type>) 04629 __glibcxx_requires_valid_range(__first, __nth); 04630 __glibcxx_requires_valid_range(__nth, __last); 04631 __glibcxx_requires_irreflexive(__first, __last); 04632 04633 if (__first == __last || __nth == __last) 04634 return; 04635 04636 std::__introselect(__first, __nth, __last, 04637 std::__lg(__last - __first) * 2, 04638 __gnu_cxx::__ops::__iter_less_iter()); 04639 } 04640 04641 /** 04642 * @brief Sort a sequence just enough to find a particular position 04643 * using a predicate for comparison. 04644 * @ingroup sorting_algorithms 04645 * @param __first An iterator. 04646 * @param __nth Another iterator. 04647 * @param __last Another iterator. 04648 * @param __comp A comparison functor. 04649 * @return Nothing. 04650 * 04651 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 04652 * is the same element that would have been in that position had the 04653 * whole sequence been sorted. The elements either side of @p *__nth are 04654 * not completely sorted, but for any iterator @e i in the range 04655 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 04656 * holds that @p __comp(*j,*i) is false. 04657 */ 04658 template<typename _RandomAccessIterator, typename _Compare> 04659 inline void 04660 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 04661 _RandomAccessIterator __last, _Compare __comp) 04662 { 04663 // concept requirements 04664 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04665 _RandomAccessIterator>) 04666 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04667 typename iterator_traits<_RandomAccessIterator>::value_type, 04668 typename iterator_traits<_RandomAccessIterator>::value_type>) 04669 __glibcxx_requires_valid_range(__first, __nth); 04670 __glibcxx_requires_valid_range(__nth, __last); 04671 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 04672 04673 if (__first == __last || __nth == __last) 04674 return; 04675 04676 std::__introselect(__first, __nth, __last, 04677 std::__lg(__last - __first) * 2, 04678 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04679 } 04680 04681 /** 04682 * @brief Sort the elements of a sequence. 04683 * @ingroup sorting_algorithms 04684 * @param __first An iterator. 04685 * @param __last Another iterator. 04686 * @return Nothing. 04687 * 04688 * Sorts the elements in the range @p [__first,__last) in ascending order, 04689 * such that for each iterator @e i in the range @p [__first,__last-1), 04690 * *(i+1)<*i is false. 04691 * 04692 * The relative ordering of equivalent elements is not preserved, use 04693 * @p stable_sort() if this is needed. 04694 */ 04695 template<typename _RandomAccessIterator> 04696 inline void 04697 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 04698 { 04699 // concept requirements 04700 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04701 _RandomAccessIterator>) 04702 __glibcxx_function_requires(_LessThanComparableConcept< 04703 typename iterator_traits<_RandomAccessIterator>::value_type>) 04704 __glibcxx_requires_valid_range(__first, __last); 04705 __glibcxx_requires_irreflexive(__first, __last); 04706 04707 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 04708 } 04709 04710 /** 04711 * @brief Sort the elements of a sequence using a predicate for comparison. 04712 * @ingroup sorting_algorithms 04713 * @param __first An iterator. 04714 * @param __last Another iterator. 04715 * @param __comp A comparison functor. 04716 * @return Nothing. 04717 * 04718 * Sorts the elements in the range @p [__first,__last) in ascending order, 04719 * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the 04720 * range @p [__first,__last-1). 04721 * 04722 * The relative ordering of equivalent elements is not preserved, use 04723 * @p stable_sort() if this is needed. 04724 */ 04725 template<typename _RandomAccessIterator, typename _Compare> 04726 inline void 04727 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 04728 _Compare __comp) 04729 { 04730 // concept requirements 04731 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04732 _RandomAccessIterator>) 04733 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04734 typename iterator_traits<_RandomAccessIterator>::value_type, 04735 typename iterator_traits<_RandomAccessIterator>::value_type>) 04736 __glibcxx_requires_valid_range(__first, __last); 04737 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 04738 04739 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04740 } 04741 04742 template<typename _InputIterator1, typename _InputIterator2, 04743 typename _OutputIterator, typename _Compare> 04744 _OutputIterator 04745 __merge(_InputIterator1 __first1, _InputIterator1 __last1, 04746 _InputIterator2 __first2, _InputIterator2 __last2, 04747 _OutputIterator __result, _Compare __comp) 04748 { 04749 while (__first1 != __last1 && __first2 != __last2) 04750 { 04751 if (__comp(__first2, __first1)) 04752 { 04753 *__result = *__first2; 04754 ++__first2; 04755 } 04756 else 04757 { 04758 *__result = *__first1; 04759 ++__first1; 04760 } 04761 ++__result; 04762 } 04763 return std::copy(__first2, __last2, 04764 std::copy(__first1, __last1, __result)); 04765 } 04766 04767 /** 04768 * @brief Merges two sorted ranges. 04769 * @ingroup sorting_algorithms 04770 * @param __first1 An iterator. 04771 * @param __first2 Another iterator. 04772 * @param __last1 Another iterator. 04773 * @param __last2 Another iterator. 04774 * @param __result An iterator pointing to the end of the merged range. 04775 * @return An iterator pointing to the first element <em>not less 04776 * than</em> @e val. 04777 * 04778 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 04779 * the sorted range @p [__result, __result + (__last1-__first1) + 04780 * (__last2-__first2)). Both input ranges must be sorted, and the 04781 * output range must not overlap with either of the input ranges. 04782 * The sort is @e stable, that is, for equivalent elements in the 04783 * two ranges, elements from the first range will always come 04784 * before elements from the second. 04785 */ 04786 template<typename _InputIterator1, typename _InputIterator2, 04787 typename _OutputIterator> 04788 inline _OutputIterator 04789 merge(_InputIterator1 __first1, _InputIterator1 __last1, 04790 _InputIterator2 __first2, _InputIterator2 __last2, 04791 _OutputIterator __result) 04792 { 04793 // concept requirements 04794 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04795 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04796 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04797 typename iterator_traits<_InputIterator1>::value_type>) 04798 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04799 typename iterator_traits<_InputIterator2>::value_type>) 04800 __glibcxx_function_requires(_LessThanOpConcept< 04801 typename iterator_traits<_InputIterator2>::value_type, 04802 typename iterator_traits<_InputIterator1>::value_type>) 04803 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 04804 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 04805 __glibcxx_requires_irreflexive2(__first1, __last1); 04806 __glibcxx_requires_irreflexive2(__first2, __last2); 04807 04808 return _GLIBCXX_STD_A::__merge(__first1, __last1, 04809 __first2, __last2, __result, 04810 __gnu_cxx::__ops::__iter_less_iter()); 04811 } 04812 04813 /** 04814 * @brief Merges two sorted ranges. 04815 * @ingroup sorting_algorithms 04816 * @param __first1 An iterator. 04817 * @param __first2 Another iterator. 04818 * @param __last1 Another iterator. 04819 * @param __last2 Another iterator. 04820 * @param __result An iterator pointing to the end of the merged range. 04821 * @param __comp A functor to use for comparisons. 04822 * @return An iterator pointing to the first element "not less 04823 * than" @e val. 04824 * 04825 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 04826 * the sorted range @p [__result, __result + (__last1-__first1) + 04827 * (__last2-__first2)). Both input ranges must be sorted, and the 04828 * output range must not overlap with either of the input ranges. 04829 * The sort is @e stable, that is, for equivalent elements in the 04830 * two ranges, elements from the first range will always come 04831 * before elements from the second. 04832 * 04833 * The comparison function should have the same effects on ordering as 04834 * the function used for the initial sort. 04835 */ 04836 template<typename _InputIterator1, typename _InputIterator2, 04837 typename _OutputIterator, typename _Compare> 04838 inline _OutputIterator 04839 merge(_InputIterator1 __first1, _InputIterator1 __last1, 04840 _InputIterator2 __first2, _InputIterator2 __last2, 04841 _OutputIterator __result, _Compare __comp) 04842 { 04843 // concept requirements 04844 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04845 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04846 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04847 typename iterator_traits<_InputIterator1>::value_type>) 04848 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04849 typename iterator_traits<_InputIterator2>::value_type>) 04850 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04851 typename iterator_traits<_InputIterator2>::value_type, 04852 typename iterator_traits<_InputIterator1>::value_type>) 04853 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 04854 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 04855 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 04856 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 04857 04858 return _GLIBCXX_STD_A::__merge(__first1, __last1, 04859 __first2, __last2, __result, 04860 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04861 } 04862 04863 template<typename _RandomAccessIterator, typename _Compare> 04864 inline void 04865 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 04866 _Compare __comp) 04867 { 04868 typedef typename iterator_traits<_RandomAccessIterator>::value_type 04869 _ValueType; 04870 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 04871 _DistanceType; 04872 04873 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf; 04874 _TmpBuf __buf(__first, __last); 04875 04876 if (__buf.begin() == 0) 04877 std::__inplace_stable_sort(__first, __last, __comp); 04878 else 04879 std::__stable_sort_adaptive(__first, __last, __buf.begin(), 04880 _DistanceType(__buf.size()), __comp); 04881 } 04882 04883 /** 04884 * @brief Sort the elements of a sequence, preserving the relative order 04885 * of equivalent elements. 04886 * @ingroup sorting_algorithms 04887 * @param __first An iterator. 04888 * @param __last Another iterator. 04889 * @return Nothing. 04890 * 04891 * Sorts the elements in the range @p [__first,__last) in ascending order, 04892 * such that for each iterator @p i in the range @p [__first,__last-1), 04893 * @p *(i+1)<*i is false. 04894 * 04895 * The relative ordering of equivalent elements is preserved, so any two 04896 * elements @p x and @p y in the range @p [__first,__last) such that 04897 * @p x<y is false and @p y<x is false will have the same relative 04898 * ordering after calling @p stable_sort(). 04899 */ 04900 template<typename _RandomAccessIterator> 04901 inline void 04902 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 04903 { 04904 // concept requirements 04905 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04906 _RandomAccessIterator>) 04907 __glibcxx_function_requires(_LessThanComparableConcept< 04908 typename iterator_traits<_RandomAccessIterator>::value_type>) 04909 __glibcxx_requires_valid_range(__first, __last); 04910 __glibcxx_requires_irreflexive(__first, __last); 04911 04912 _GLIBCXX_STD_A::__stable_sort(__first, __last, 04913 __gnu_cxx::__ops::__iter_less_iter()); 04914 } 04915 04916 /** 04917 * @brief Sort the elements of a sequence using a predicate for comparison, 04918 * preserving the relative order of equivalent elements. 04919 * @ingroup sorting_algorithms 04920 * @param __first An iterator. 04921 * @param __last Another iterator. 04922 * @param __comp A comparison functor. 04923 * @return Nothing. 04924 * 04925 * Sorts the elements in the range @p [__first,__last) in ascending order, 04926 * such that for each iterator @p i in the range @p [__first,__last-1), 04927 * @p __comp(*(i+1),*i) is false. 04928 * 04929 * The relative ordering of equivalent elements is preserved, so any two 04930 * elements @p x and @p y in the range @p [__first,__last) such that 04931 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same 04932 * relative ordering after calling @p stable_sort(). 04933 */ 04934 template<typename _RandomAccessIterator, typename _Compare> 04935 inline void 04936 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 04937 _Compare __comp) 04938 { 04939 // concept requirements 04940 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04941 _RandomAccessIterator>) 04942 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04943 typename iterator_traits<_RandomAccessIterator>::value_type, 04944 typename iterator_traits<_RandomAccessIterator>::value_type>) 04945 __glibcxx_requires_valid_range(__first, __last); 04946 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 04947 04948 _GLIBCXX_STD_A::__stable_sort(__first, __last, 04949 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04950 } 04951 04952 template<typename _InputIterator1, typename _InputIterator2, 04953 typename _OutputIterator, 04954 typename _Compare> 04955 _OutputIterator 04956 __set_union(_InputIterator1 __first1, _InputIterator1 __last1, 04957 _InputIterator2 __first2, _InputIterator2 __last2, 04958 _OutputIterator __result, _Compare __comp) 04959 { 04960 while (__first1 != __last1 && __first2 != __last2) 04961 { 04962 if (__comp(__first1, __first2)) 04963 { 04964 *__result = *__first1; 04965 ++__first1; 04966 } 04967 else if (__comp(__first2, __first1)) 04968 { 04969 *__result = *__first2; 04970 ++__first2; 04971 } 04972 else 04973 { 04974 *__result = *__first1; 04975 ++__first1; 04976 ++__first2; 04977 } 04978 ++__result; 04979 } 04980 return std::copy(__first2, __last2, 04981 std::copy(__first1, __last1, __result)); 04982 } 04983 04984 /** 04985 * @brief Return the union of two sorted ranges. 04986 * @ingroup set_algorithms 04987 * @param __first1 Start of first range. 04988 * @param __last1 End of first range. 04989 * @param __first2 Start of second range. 04990 * @param __last2 End of second range. 04991 * @return End of the output range. 04992 * @ingroup set_algorithms 04993 * 04994 * This operation iterates over both ranges, copying elements present in 04995 * each range in order to the output range. Iterators increment for each 04996 * range. When the current element of one range is less than the other, 04997 * that element is copied and the iterator advanced. If an element is 04998 * contained in both ranges, the element from the first range is copied and 04999 * both ranges advance. The output range may not overlap either input 05000 * range. 05001 */ 05002 template<typename _InputIterator1, typename _InputIterator2, 05003 typename _OutputIterator> 05004 inline _OutputIterator 05005 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 05006 _InputIterator2 __first2, _InputIterator2 __last2, 05007 _OutputIterator __result) 05008 { 05009 // concept requirements 05010 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05011 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05012 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05013 typename iterator_traits<_InputIterator1>::value_type>) 05014 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05015 typename iterator_traits<_InputIterator2>::value_type>) 05016 __glibcxx_function_requires(_LessThanOpConcept< 05017 typename iterator_traits<_InputIterator1>::value_type, 05018 typename iterator_traits<_InputIterator2>::value_type>) 05019 __glibcxx_function_requires(_LessThanOpConcept< 05020 typename iterator_traits<_InputIterator2>::value_type, 05021 typename iterator_traits<_InputIterator1>::value_type>) 05022 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05023 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05024 __glibcxx_requires_irreflexive2(__first1, __last1); 05025 __glibcxx_requires_irreflexive2(__first2, __last2); 05026 05027 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 05028 __first2, __last2, __result, 05029 __gnu_cxx::__ops::__iter_less_iter()); 05030 } 05031 05032 /** 05033 * @brief Return the union of two sorted ranges using a comparison functor. 05034 * @ingroup set_algorithms 05035 * @param __first1 Start of first range. 05036 * @param __last1 End of first range. 05037 * @param __first2 Start of second range. 05038 * @param __last2 End of second range. 05039 * @param __comp The comparison functor. 05040 * @return End of the output range. 05041 * @ingroup set_algorithms 05042 * 05043 * This operation iterates over both ranges, copying elements present in 05044 * each range in order to the output range. Iterators increment for each 05045 * range. When the current element of one range is less than the other 05046 * according to @p __comp, that element is copied and the iterator advanced. 05047 * If an equivalent element according to @p __comp is contained in both 05048 * ranges, the element from the first range is copied and both ranges 05049 * advance. The output range may not overlap either input range. 05050 */ 05051 template<typename _InputIterator1, typename _InputIterator2, 05052 typename _OutputIterator, typename _Compare> 05053 inline _OutputIterator 05054 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 05055 _InputIterator2 __first2, _InputIterator2 __last2, 05056 _OutputIterator __result, _Compare __comp) 05057 { 05058 // concept requirements 05059 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05060 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05061 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05062 typename iterator_traits<_InputIterator1>::value_type>) 05063 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05064 typename iterator_traits<_InputIterator2>::value_type>) 05065 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05066 typename iterator_traits<_InputIterator1>::value_type, 05067 typename iterator_traits<_InputIterator2>::value_type>) 05068 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05069 typename iterator_traits<_InputIterator2>::value_type, 05070 typename iterator_traits<_InputIterator1>::value_type>) 05071 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05072 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05073 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 05074 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 05075 05076 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 05077 __first2, __last2, __result, 05078 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05079 } 05080 05081 template<typename _InputIterator1, typename _InputIterator2, 05082 typename _OutputIterator, 05083 typename _Compare> 05084 _OutputIterator 05085 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05086 _InputIterator2 __first2, _InputIterator2 __last2, 05087 _OutputIterator __result, _Compare __comp) 05088 { 05089 while (__first1 != __last1 && __first2 != __last2) 05090 if (__comp(__first1, __first2)) 05091 ++__first1; 05092 else if (__comp(__first2, __first1)) 05093 ++__first2; 05094 else 05095 { 05096 *__result = *__first1; 05097 ++__first1; 05098 ++__first2; 05099 ++__result; 05100 } 05101 return __result; 05102 } 05103 05104 /** 05105 * @brief Return the intersection of two sorted ranges. 05106 * @ingroup set_algorithms 05107 * @param __first1 Start of first range. 05108 * @param __last1 End of first range. 05109 * @param __first2 Start of second range. 05110 * @param __last2 End of second range. 05111 * @return End of the output range. 05112 * @ingroup set_algorithms 05113 * 05114 * This operation iterates over both ranges, copying elements present in 05115 * both ranges in order to the output range. Iterators increment for each 05116 * range. When the current element of one range is less than the other, 05117 * that iterator advances. If an element is contained in both ranges, the 05118 * element from the first range is copied and both ranges advance. The 05119 * output range may not overlap either input range. 05120 */ 05121 template<typename _InputIterator1, typename _InputIterator2, 05122 typename _OutputIterator> 05123 inline _OutputIterator 05124 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05125 _InputIterator2 __first2, _InputIterator2 __last2, 05126 _OutputIterator __result) 05127 { 05128 // concept requirements 05129 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05130 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05131 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05132 typename iterator_traits<_InputIterator1>::value_type>) 05133 __glibcxx_function_requires(_LessThanOpConcept< 05134 typename iterator_traits<_InputIterator1>::value_type, 05135 typename iterator_traits<_InputIterator2>::value_type>) 05136 __glibcxx_function_requires(_LessThanOpConcept< 05137 typename iterator_traits<_InputIterator2>::value_type, 05138 typename iterator_traits<_InputIterator1>::value_type>) 05139 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05140 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05141 __glibcxx_requires_irreflexive2(__first1, __last1); 05142 __glibcxx_requires_irreflexive2(__first2, __last2); 05143 05144 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 05145 __first2, __last2, __result, 05146 __gnu_cxx::__ops::__iter_less_iter()); 05147 } 05148 05149 /** 05150 * @brief Return the intersection of two sorted ranges using comparison 05151 * functor. 05152 * @ingroup set_algorithms 05153 * @param __first1 Start of first range. 05154 * @param __last1 End of first range. 05155 * @param __first2 Start of second range. 05156 * @param __last2 End of second range. 05157 * @param __comp The comparison functor. 05158 * @return End of the output range. 05159 * @ingroup set_algorithms 05160 * 05161 * This operation iterates over both ranges, copying elements present in 05162 * both ranges in order to the output range. Iterators increment for each 05163 * range. When the current element of one range is less than the other 05164 * according to @p __comp, that iterator advances. If an element is 05165 * contained in both ranges according to @p __comp, the element from the 05166 * first range is copied and both ranges advance. The output range may not 05167 * overlap either input range. 05168 */ 05169 template<typename _InputIterator1, typename _InputIterator2, 05170 typename _OutputIterator, typename _Compare> 05171 inline _OutputIterator 05172 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05173 _InputIterator2 __first2, _InputIterator2 __last2, 05174 _OutputIterator __result, _Compare __comp) 05175 { 05176 // concept requirements 05177 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05178 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05179 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05180 typename iterator_traits<_InputIterator1>::value_type>) 05181 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05182 typename iterator_traits<_InputIterator1>::value_type, 05183 typename iterator_traits<_InputIterator2>::value_type>) 05184 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05185 typename iterator_traits<_InputIterator2>::value_type, 05186 typename iterator_traits<_InputIterator1>::value_type>) 05187 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05188 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05189 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 05190 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 05191 05192 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 05193 __first2, __last2, __result, 05194 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05195 } 05196 05197 template<typename _InputIterator1, typename _InputIterator2, 05198 typename _OutputIterator, 05199 typename _Compare> 05200 _OutputIterator 05201 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05202 _InputIterator2 __first2, _InputIterator2 __last2, 05203 _OutputIterator __result, _Compare __comp) 05204 { 05205 while (__first1 != __last1 && __first2 != __last2) 05206 if (__comp(__first1, __first2)) 05207 { 05208 *__result = *__first1; 05209 ++__first1; 05210 ++__result; 05211 } 05212 else if (__comp(__first2, __first1)) 05213 ++__first2; 05214 else 05215 { 05216 ++__first1; 05217 ++__first2; 05218 } 05219 return std::copy(__first1, __last1, __result); 05220 } 05221 05222 /** 05223 * @brief Return the difference of two sorted ranges. 05224 * @ingroup set_algorithms 05225 * @param __first1 Start of first range. 05226 * @param __last1 End of first range. 05227 * @param __first2 Start of second range. 05228 * @param __last2 End of second range. 05229 * @return End of the output range. 05230 * @ingroup set_algorithms 05231 * 05232 * This operation iterates over both ranges, copying elements present in 05233 * the first range but not the second in order to the output range. 05234 * Iterators increment for each range. When the current element of the 05235 * first range is less than the second, that element is copied and the 05236 * iterator advances. If the current element of the second range is less, 05237 * the iterator advances, but no element is copied. If an element is 05238 * contained in both ranges, no elements are copied and both ranges 05239 * advance. The output range may not overlap either input range. 05240 */ 05241 template<typename _InputIterator1, typename _InputIterator2, 05242 typename _OutputIterator> 05243 inline _OutputIterator 05244 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05245 _InputIterator2 __first2, _InputIterator2 __last2, 05246 _OutputIterator __result) 05247 { 05248 // concept requirements 05249 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05250 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05251 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05252 typename iterator_traits<_InputIterator1>::value_type>) 05253 __glibcxx_function_requires(_LessThanOpConcept< 05254 typename iterator_traits<_InputIterator1>::value_type, 05255 typename iterator_traits<_InputIterator2>::value_type>) 05256 __glibcxx_function_requires(_LessThanOpConcept< 05257 typename iterator_traits<_InputIterator2>::value_type, 05258 typename iterator_traits<_InputIterator1>::value_type>) 05259 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05260 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05261 __glibcxx_requires_irreflexive2(__first1, __last1); 05262 __glibcxx_requires_irreflexive2(__first2, __last2); 05263 05264 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 05265 __first2, __last2, __result, 05266 __gnu_cxx::__ops::__iter_less_iter()); 05267 } 05268 05269 /** 05270 * @brief Return the difference of two sorted ranges using comparison 05271 * functor. 05272 * @ingroup set_algorithms 05273 * @param __first1 Start of first range. 05274 * @param __last1 End of first range. 05275 * @param __first2 Start of second range. 05276 * @param __last2 End of second range. 05277 * @param __comp The comparison functor. 05278 * @return End of the output range. 05279 * @ingroup set_algorithms 05280 * 05281 * This operation iterates over both ranges, copying elements present in 05282 * the first range but not the second in order to the output range. 05283 * Iterators increment for each range. When the current element of the 05284 * first range is less than the second according to @p __comp, that element 05285 * is copied and the iterator advances. If the current element of the 05286 * second range is less, no element is copied and the iterator advances. 05287 * If an element is contained in both ranges according to @p __comp, no 05288 * elements are copied and both ranges advance. The output range may not 05289 * overlap either input range. 05290 */ 05291 template<typename _InputIterator1, typename _InputIterator2, 05292 typename _OutputIterator, typename _Compare> 05293 inline _OutputIterator 05294 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05295 _InputIterator2 __first2, _InputIterator2 __last2, 05296 _OutputIterator __result, _Compare __comp) 05297 { 05298 // concept requirements 05299 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05300 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05301 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05302 typename iterator_traits<_InputIterator1>::value_type>) 05303 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05304 typename iterator_traits<_InputIterator1>::value_type, 05305 typename iterator_traits<_InputIterator2>::value_type>) 05306 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05307 typename iterator_traits<_InputIterator2>::value_type, 05308 typename iterator_traits<_InputIterator1>::value_type>) 05309 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05310 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05311 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 05312 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 05313 05314 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 05315 __first2, __last2, __result, 05316 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05317 } 05318 05319 template<typename _InputIterator1, typename _InputIterator2, 05320 typename _OutputIterator, 05321 typename _Compare> 05322 _OutputIterator 05323 __set_symmetric_difference(_InputIterator1 __first1, 05324 _InputIterator1 __last1, 05325 _InputIterator2 __first2, 05326 _InputIterator2 __last2, 05327 _OutputIterator __result, 05328 _Compare __comp) 05329 { 05330 while (__first1 != __last1 && __first2 != __last2) 05331 if (__comp(__first1, __first2)) 05332 { 05333 *__result = *__first1; 05334 ++__first1; 05335 ++__result; 05336 } 05337 else if (__comp(__first2, __first1)) 05338 { 05339 *__result = *__first2; 05340 ++__first2; 05341 ++__result; 05342 } 05343 else 05344 { 05345 ++__first1; 05346 ++__first2; 05347 } 05348 return std::copy(__first2, __last2, 05349 std::copy(__first1, __last1, __result)); 05350 } 05351 05352 /** 05353 * @brief Return the symmetric difference of two sorted ranges. 05354 * @ingroup set_algorithms 05355 * @param __first1 Start of first range. 05356 * @param __last1 End of first range. 05357 * @param __first2 Start of second range. 05358 * @param __last2 End of second range. 05359 * @return End of the output range. 05360 * @ingroup set_algorithms 05361 * 05362 * This operation iterates over both ranges, copying elements present in 05363 * one range but not the other in order to the output range. Iterators 05364 * increment for each range. When the current element of one range is less 05365 * than the other, that element is copied and the iterator advances. If an 05366 * element is contained in both ranges, no elements are copied and both 05367 * ranges advance. The output range may not overlap either input range. 05368 */ 05369 template<typename _InputIterator1, typename _InputIterator2, 05370 typename _OutputIterator> 05371 inline _OutputIterator 05372 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05373 _InputIterator2 __first2, _InputIterator2 __last2, 05374 _OutputIterator __result) 05375 { 05376 // concept requirements 05377 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05378 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05379 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05380 typename iterator_traits<_InputIterator1>::value_type>) 05381 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05382 typename iterator_traits<_InputIterator2>::value_type>) 05383 __glibcxx_function_requires(_LessThanOpConcept< 05384 typename iterator_traits<_InputIterator1>::value_type, 05385 typename iterator_traits<_InputIterator2>::value_type>) 05386 __glibcxx_function_requires(_LessThanOpConcept< 05387 typename iterator_traits<_InputIterator2>::value_type, 05388 typename iterator_traits<_InputIterator1>::value_type>) 05389 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05390 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05391 __glibcxx_requires_irreflexive2(__first1, __last1); 05392 __glibcxx_requires_irreflexive2(__first2, __last2); 05393 05394 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 05395 __first2, __last2, __result, 05396 __gnu_cxx::__ops::__iter_less_iter()); 05397 } 05398 05399 /** 05400 * @brief Return the symmetric difference of two sorted ranges using 05401 * comparison functor. 05402 * @ingroup set_algorithms 05403 * @param __first1 Start of first range. 05404 * @param __last1 End of first range. 05405 * @param __first2 Start of second range. 05406 * @param __last2 End of second range. 05407 * @param __comp The comparison functor. 05408 * @return End of the output range. 05409 * @ingroup set_algorithms 05410 * 05411 * This operation iterates over both ranges, copying elements present in 05412 * one range but not the other in order to the output range. Iterators 05413 * increment for each range. When the current element of one range is less 05414 * than the other according to @p comp, that element is copied and the 05415 * iterator advances. If an element is contained in both ranges according 05416 * to @p __comp, no elements are copied and both ranges advance. The output 05417 * range may not overlap either input range. 05418 */ 05419 template<typename _InputIterator1, typename _InputIterator2, 05420 typename _OutputIterator, typename _Compare> 05421 inline _OutputIterator 05422 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05423 _InputIterator2 __first2, _InputIterator2 __last2, 05424 _OutputIterator __result, 05425 _Compare __comp) 05426 { 05427 // concept requirements 05428 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05429 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05430 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05431 typename iterator_traits<_InputIterator1>::value_type>) 05432 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05433 typename iterator_traits<_InputIterator2>::value_type>) 05434 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05435 typename iterator_traits<_InputIterator1>::value_type, 05436 typename iterator_traits<_InputIterator2>::value_type>) 05437 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05438 typename iterator_traits<_InputIterator2>::value_type, 05439 typename iterator_traits<_InputIterator1>::value_type>) 05440 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05441 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05442 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 05443 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 05444 05445 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 05446 __first2, __last2, __result, 05447 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05448 } 05449 05450 template<typename _ForwardIterator, typename _Compare> 05451 _GLIBCXX14_CONSTEXPR 05452 _ForwardIterator 05453 __min_element(_ForwardIterator __first, _ForwardIterator __last, 05454 _Compare __comp) 05455 { 05456 if (__first == __last) 05457 return __first; 05458 _ForwardIterator __result = __first; 05459 while (++__first != __last) 05460 if (__comp(__first, __result)) 05461 __result = __first; 05462 return __result; 05463 } 05464 05465 /** 05466 * @brief Return the minimum element in a range. 05467 * @ingroup sorting_algorithms 05468 * @param __first Start of range. 05469 * @param __last End of range. 05470 * @return Iterator referencing the first instance of the smallest value. 05471 */ 05472 template<typename _ForwardIterator> 05473 _GLIBCXX14_CONSTEXPR 05474 _ForwardIterator 05475 inline min_element(_ForwardIterator __first, _ForwardIterator __last) 05476 { 05477 // concept requirements 05478 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05479 __glibcxx_function_requires(_LessThanComparableConcept< 05480 typename iterator_traits<_ForwardIterator>::value_type>) 05481 __glibcxx_requires_valid_range(__first, __last); 05482 __glibcxx_requires_irreflexive(__first, __last); 05483 05484 return _GLIBCXX_STD_A::__min_element(__first, __last, 05485 __gnu_cxx::__ops::__iter_less_iter()); 05486 } 05487 05488 /** 05489 * @brief Return the minimum element in a range using comparison functor. 05490 * @ingroup sorting_algorithms 05491 * @param __first Start of range. 05492 * @param __last End of range. 05493 * @param __comp Comparison functor. 05494 * @return Iterator referencing the first instance of the smallest value 05495 * according to __comp. 05496 */ 05497 template<typename _ForwardIterator, typename _Compare> 05498 _GLIBCXX14_CONSTEXPR 05499 inline _ForwardIterator 05500 min_element(_ForwardIterator __first, _ForwardIterator __last, 05501 _Compare __comp) 05502 { 05503 // concept requirements 05504 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05505 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05506 typename iterator_traits<_ForwardIterator>::value_type, 05507 typename iterator_traits<_ForwardIterator>::value_type>) 05508 __glibcxx_requires_valid_range(__first, __last); 05509 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 05510 05511 return _GLIBCXX_STD_A::__min_element(__first, __last, 05512 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05513 } 05514 05515 template<typename _ForwardIterator, typename _Compare> 05516 _GLIBCXX14_CONSTEXPR 05517 _ForwardIterator 05518 __max_element(_ForwardIterator __first, _ForwardIterator __last, 05519 _Compare __comp) 05520 { 05521 if (__first == __last) return __first; 05522 _ForwardIterator __result = __first; 05523 while (++__first != __last) 05524 if (__comp(__result, __first)) 05525 __result = __first; 05526 return __result; 05527 } 05528 05529 /** 05530 * @brief Return the maximum element in a range. 05531 * @ingroup sorting_algorithms 05532 * @param __first Start of range. 05533 * @param __last End of range. 05534 * @return Iterator referencing the first instance of the largest value. 05535 */ 05536 template<typename _ForwardIterator> 05537 _GLIBCXX14_CONSTEXPR 05538 inline _ForwardIterator 05539 max_element(_ForwardIterator __first, _ForwardIterator __last) 05540 { 05541 // concept requirements 05542 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05543 __glibcxx_function_requires(_LessThanComparableConcept< 05544 typename iterator_traits<_ForwardIterator>::value_type>) 05545 __glibcxx_requires_valid_range(__first, __last); 05546 __glibcxx_requires_irreflexive(__first, __last); 05547 05548 return _GLIBCXX_STD_A::__max_element(__first, __last, 05549 __gnu_cxx::__ops::__iter_less_iter()); 05550 } 05551 05552 /** 05553 * @brief Return the maximum element in a range using comparison functor. 05554 * @ingroup sorting_algorithms 05555 * @param __first Start of range. 05556 * @param __last End of range. 05557 * @param __comp Comparison functor. 05558 * @return Iterator referencing the first instance of the largest value 05559 * according to __comp. 05560 */ 05561 template<typename _ForwardIterator, typename _Compare> 05562 _GLIBCXX14_CONSTEXPR 05563 inline _ForwardIterator 05564 max_element(_ForwardIterator __first, _ForwardIterator __last, 05565 _Compare __comp) 05566 { 05567 // concept requirements 05568 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05569 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05570 typename iterator_traits<_ForwardIterator>::value_type, 05571 typename iterator_traits<_ForwardIterator>::value_type>) 05572 __glibcxx_requires_valid_range(__first, __last); 05573 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 05574 05575 return _GLIBCXX_STD_A::__max_element(__first, __last, 05576 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05577 } 05578 05579 _GLIBCXX_END_NAMESPACE_ALGO 05580 } // namespace std 05581 05582 #endif /* _STL_ALGO_H */