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