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